洛谷OJ：P1726 上白泽慧音(强连通分量水题)

分析：给定一个有向图，求出最大的强连通分量

#include <iostream>
#include <cstdio>
#include <vector>
#define Min(a,b) a<b?a:b
#define Max(a,b) a>b?a:b
using namespace std;

const int maxn = 1e5+10;
/*********强连通分量*********/
int dfn[maxn], low[maxn], id[maxn], cnt[maxn], ins[maxn], Stack[maxn];
int sum, top = -1, depth;
int n, m;
/****************************/
vector<int> G[maxn];
vector<int> g[maxn];
vector<int> g_[maxn];
int Top() { return Stack[top]; }
void Push(int a) { Stack[++top] = a; ins[a] = 1; }
void Pop() { ins[Top()] = 0; top--; }

void tanjar(int cur) {
    dfn[cur] = low[cur] = ++depth;
    Push(cur);
    int v;
    for(int i = 0; i < G[cur].size(); i++) {
        v = G[cur][i];
        if(!dfn[v]) {
            tanjar(v);
            low[cur] = min(low[cur], low[v]);
        }
        else if(ins[v]) {
            low[cur] = min(low[cur], low[v]);
        }
    }
    if(dfn[cur] == low[cur]) {
        int temp;
        id[cur] = ++sum;
        cnt[sum]++;
        while((temp = Top()) != cur) {
            id[temp] = sum;
            cnt[sum]++;
            Pop();
        }
        Pop();
    }
}

int main() {
    int t1, t2, t3;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d %d %d", &t1, &t2, &t3);
        G[t1].push_back(t2);
        if(t3 == 2) G[t2].push_back(t1);
    }
    for(int i = 1; i <= n; i++) if(!dfn[i]) tanjar(i);
    int ind, Max = 0;
    for(int i = 1; i <= sum; i++) {
        if(cnt[i] > Max) {
            ind = i;
            Max = cnt[i];
        }
    }
    //for(int i = 1; i <= n; i++) printf("%d'id is %d   ", i, id[i]); printf("\n");
    printf("%d\n", Max);
    for(int i = 1; i <= n; i++) if(id[i] == ind) printf("%d ", i);
    return 0;
}