首页 > 代码库 > fzu2181(点的双连通分量+求奇环)

fzu2181(点的双连通分量+求奇环)

求出每个点双连通分量,如果在一个点双连通分量中有奇环,则这个分量每个点都在一个奇环中。  关键是要知道怎么求点双连通分量以及点双连通的性质。

 

fzu2181 http://acm.fzu.edu.cn/problem.php?pid=2181

 

#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define N 1100int n,m,k;int g[N][N];int vis[N];int height[N];int stk[N];int deep,top;int mark[N];int save[N]; //用来记录特殊状态int ans;int dfs(int s,int num){    vis[s]=deep++;    stk[top++]=s;    height[s]=num;    int mi=vis[s];    for(int i=1;i<=n;i++)    {        if(g[s][i]==0) continue;        if(vis[i]==-1) //这个点未被访问        {            dfs(i,num+1);            if( vis[i]>=vis[s] )//表示这个圈与世无争,必须单独处理掉            {                //开始处理!                int cnt=0;                int tcnt=0;                int flag=0;                while(stk[top-1]!=s)                {                    cnt++;                    if(mark[stk[top-1]]==1) flag=1;//表示这一堆有奇环                    if(save[stk[top-1]]==1) tcnt++;                    top--;                }                if(flag==1)//这一堆不存在奇环                {                    save[s]=1;                    ans += cnt+1-tcnt;                }            }            else            {                mi = min(mi,vis[i]);            }        }        else        {            mi=min(mi,vis[i]);//找当前能到达最上方的点            if( (height[s]-height[i])%2==0 )//表示当前点在一个奇环中                mark[s]=1;        }    }    vis[s]=mi;    return vis[s];}int main(){    int T;    scanf("%d",&T);    while(T--)    {        scanf("%d%d%d",&n,&m,&k);        memset(g,0,sizeof(g));        for(int i=0;i<m;i++)        {            int x,y;            scanf("%d%d",&x,&y);            g[x][y]=g[y][x]=1;        }        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++)            {                if(i==j) g[i][j]=0;                else if(g[i][j]==1) g[i][j]=0;                else g[i][j]=1;            }        //构建逆图        memset(vis,-1,sizeof(vis));        memset(save,0,sizeof(save));        memset(mark,0,sizeof(mark));        deep=0;        top=0;        ans=0;//表示有多少不能参与游戏        for(int i=1;i<=n;i++)        {            if(vis[i]==-1)            {                dfs(i,0);            }        }        if(ans<k) printf("What a Pity.\n");        else printf("Let‘s Fire!\n");    }    return 0;}

 

fzu2181(点的双连通分量+求奇环)