qianglt.cpp

在强连通分支算法中

#include<iostream>

using namespace std;
#define MAXN 10001

bool map[MAXN][MAXN];
short now[MAXN],low[MAXN];
short st[MAXN],sp;
short color[MAXN],col;
int t_now; 
bool ans[MAXN][MAXN];

void dfs(int i,int n)
{
        low[i] = now[i] = ++t_now;
        st[sp++] = i;
        int k;
        for(int j = 1;j <= n; ++j)
        {
                if(map[i][j])
                {
                        if(!now[j])
                        {
                                dfs(j,n);
                                if(low[j] < low[i])
                                        low[i] = low[j];
                        }
                        else if (now[j] < now[i]){
                                for (k = 0; k < sp && st[k] != j; k++);
                                if (k < t_now && now[j] < low[i])
                                        low[i] = now[j];
                        }
                }
        }
        if(low[i] == now[i])
        {
                while(1)
                {
                        if(st[sp] == i)break;
                        color[st[sp - 1]] = col;
                        sp--;        
                }
                col++;
        }
}
int main()
{
        //        freopen("data.txt","r",stdin);
    
        int n,m;
        int i,j;
        int a,b;
        
        scanf("%d%d",&n,&m);
        col = 1;
        for(i = 1; i <= n; ++i)
        {
                now[i] = 0;
                low[i] = 0;
                color[i] = 0;
                for(j = 1; j <= n; ++j){map[i][j] = 0;ans[i][j] = 0;}
        }
        while(m--)
        {
                scanf("%d%d",&a,&b);
                map[a][b] = 1;
        }
        for(i = 1; i <= n; ++i)
        {
                if(now[i] == 0)
                {
                        sp = 0;
                        t_now = 0;
                        dfs(i,n);
                }
        }
        memset(st,0,sizeof(st));
        for(i = 1; i <= n; ++i)
                for(j = 1; j <= n; ++j)
                        if(map[i][j] && !ans[color[i]][color[j]] && color[i] != color[j])
                        {
                                ans[color[i]][color[j]] = 1;
                                st[color[i]]++;
                        }
                        int die = 0;
                        int temp ;
                        int aaa = 0;
                        for(i = 1 ;i < col; i++)if(!st[i]){die++;temp = i;}
                        if(die != 1)cout<<0<<endl;
                        else 
                        {
                                for(j = 1; j <= n; ++j)if(color[j] == temp)aaa++;
                                printf("%d\n",aaa);
                        }
        return 0;
}