强连通分量 Kosaraju和Tarjan算法

佚名 6年前 (2019-04-20) 随笔 1977人围观抢沙发百度已收录

#include<iostream>
#include<queue>
#include<list>
#include<vector>
#include<cstring>
#include<set>
#include<stack>
#include<map>
#include<cmath>
#include<algorithm>
#include<string>
#include<stdio.h>
using namespace std;
typedef long long ll;
#define MS(x,i) memset(x,i,sizeof(x))
#define rep(i,s,e) for(int i=s; i<=e; i++)
#define sc(a) scanf("%d",&a)
#define scl(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%d %d", &a, &b)
#define debug printf("debug......\n");
#define pfd(x) printf("%d\n",x)
#define pfl(x) printf("%lld\n",x)
const double eps=1e-8;
const double PI = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x7fffffff;
const int maxn = 5e4+10;
int dx[4] = {0, 0, 1, -1};
int dy[4]  = {1, -1, 0 , 0};

int n,m;//n个顶点m条边
//链式前向星基本操作
int cnt;
int head[maxn];
struct node{
    int v,nxt;
}edge[maxn<<1];

void addEdge(int u, int v){
    edge[cnt].v = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt++; 
}

int idx;//栈指针
int vis[maxn];//访问标记
int low[maxn];//low值
int dfn[maxn];//dfn值
int dfs_num;//dfs计数

int CN;//强连通分量的个数
int size[maxn];//各个强连通分量的size
int dye[maxn];//每个顶点属于哪一个强连通分量
int stak[maxn];
void init(){
    MS(head , 0);
    cnt = 1;

    idx =  0;
    MS(vis , 0);
    dfs_num = 0;
    CN = 0;
    MS(size , 0);
    MS(dye , 0);
}


void tarjan(int pos){
    stak[++idx] = pos;//入栈
    vis[pos] = 1;//标记
    low[pos] = dfn[pos] = ++dfs_num;//计数
    for(int i=head[pos]; i; i=edge[i].nxt){
        int v = edge[i].v;
        if(!dfn[v]){//如果这个点不在栈中
            tarjan(v);//继续tarjan
            //回溯更新low值保证当前结点是以 自己为根节点的子树中low值最小
            low[pos] = min(low[pos] , low[v]);
        }
        //如果已经被访问过且在栈中 则更新其low值为 它当前的low值和孩子结点的dfn值较小的一个
        else if(vis[v]) low[pos] = min(low[pos] , dfn[v]);
    }
    //如果low值和dfn值相等，那么说明栈中当前结点及其以上的结点是处于同一个强连通分量的
    if(dfn[pos] == low[pos]){
        vis[pos] = 0;//清除标记
        //pos结点被染色 
        dye[pos] = ++CN;//CN记录当前强连通分量的序号 也是强连通分量的个数
        size[CN]++; //该强联通分量的size加1
        //一个环
        while(pos != stak[idx]){
            vis[stak[idx]] =  0;//清除标记
            size[CN]++;
            dye[stak[idx]] = CN;//染色成CN
            idx--;//弹栈 下一个
        }
        idx--; //最后留下的是pos 也弹出去
    }
}


void solve(){
    rep(i , 1, n){
        if(!dye[i]) tarjan(i);
    }
    int pos,msz=-1;
    rep(i , 1, n){
        if(size[dye[i]] > msz){
            msz = size[dye[i]];
            pos = dye[i];
        }
    }
    cout<<msz<<endl;
    rep(i ,1 , n){
        if(dye[i] == pos) cout<<i<<" ";
    }
    cout<<endl;

}

int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        init();
        int x,y,z;
        rep(i , 1, m){
            cin>>x>>y>>z;
            addEdge(x,y);
            if(z == 2){
                addEdge(y , x);
            }
        }
        solve();
    }
    

    return 0;
}