题目地址：洛谷：【P1726】上白泽慧音 – 洛谷

题目描述

在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B)和(B,A)同时满足时，我们认为A,B是绝对连通的，记为<A,B>。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄X,Y都满足<X,Y>。现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在1,3,4和2,5,6这两个最大连通区域时，输出的是1,3,4。

输入输出格式

输入格式：
第1行：两个正整数N,M
第2..M+1行：每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路，t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。

输出格式：
第1行： 1个整数，表示最大的绝对连通区域包含的村庄个数。
第2行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。

输入输出样例

输入样例#1：

5 5
1 2 1
1 3 2
2 4 2
5 1 2
3 5 1

输出样例#1：

3
1 3 5

说明

对于60%的数据：N <= 200且M <= 10,000
对于100%的数据：N <= 5,000且M <= 50,000

题解

复习一下Tarjan强连通分量算法。是裸的找最大强连通分量的题。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cmath>
#include <cctype>

#include <vector>
#include <set>
#include <stack>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 10005;

std::vector<int> gra[MAXN];

int n, m;

int dfn[MAXN], low[MAXN], clk;
std::set<int> scc;
int sno[MAXN], ssiz[MAXN], scnt;
bool insta[MAXN];
std::stack<int> sta;

inline void tarjan(int u) {
    dfn[u] = low[u] = clk++; 
    sta.push(u); insta[u] = true;
    for(int v : gra[u]) {
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if(insta[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]) {
        scnt++;
        int p;
        do {
            p = sta.top(); sta.pop();
            sno[p] = scnt;
            ssiz[scnt]++;
            insta[p] = false;
        } while(p != u);
        if(scc.empty() || ssiz[scnt] > ssiz[*scc.begin()]) {
            scc.clear(); scc.insert(scnt);
        } else if(ssiz[scnt] == ssiz[*scc.begin()]) {
            scc.insert(scnt);
        }
    }
}

int a, b, t;

int main() {
    n = readint(); m = readint();
    while(m--) {
        a = readint(); b = readint(); t = readint();
        gra[a].push_back(b);
        if(t == 2) gra[b].push_back(a);
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i);
    }
    printf("%d\n", ssiz[*scc.begin()]);
    int tar = 0;
    for(int i = 1; i <= n; i++) {
        if(!tar && scc.count(sno[i])) tar = sno[i];
        if(sno[i] == tar) printf("%d ", i);
    }
    return 0;
}