P1726 上白泽慧音

tarjan模板题，从第一个结点开始挨个求极大连通分量，完了之后，按顺序找第一个出现的结点数最多的极大连通分量就是答案，排序输出即可。

#include<iostream>
#include<vector>
#include<stack>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 5010, M = 100010; 

int n, m;
int h[N], e[M], ne[M], idx;
vector<vector<int>> v;

int dfn[N], low[N], instk[N], nidx;
stack<int> stk;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void tarjan(int u){
    dfn[u] = low[u] = ++ nidx;
    stk.push(u);
    instk[u] = 1;
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(dfn[j] == 0){
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }else if(dfn[j] < low[u] && instk[j])
            low[u] = dfn[j];
    }
    
    if(low[u] == dfn[u]){
        vector<int> t;
        do{
            int top = stk.top();
            stk.pop();
            instk[top] = 0;
            t.push_back(top);
        }while(t.back() != u);
        
        v.push_back(t);
    }
}


int main(){
    memset(h, -1, sizeof h);
    
    cin >> n >> m;
    
    while(m --){
        int a, b, t;
        
        cin >> a >> b >> t;
        
        add(a, b);
        if(t == 2) add(b, a);
    }
    
    for(int i = 1; i <= n; i ++)
        if(dfn[i] == 0) tarjan(i);
    
    int maxv = 0;
    
    for(auto t : v) maxv = max(maxv, (int) t.size());
    for(auto t : v)
        if(t.size() == maxv){
            sort(t.begin(), t.end());
            cout << t.size() << endl;
            for(int i = 0; i < t.size(); i ++) cout << t[i] << ' ';
            break;
        }
        
    return 0;
}