解题思路
这一眼看上去就知道要求最大连通分量。用Tarjan算法进行求解，关键就是怎么按照字典序输出。从Tarjan的搜索顺序来看，搜出来的东西就是按照字典序来的。越往后面的字典序越大。
所以我们直接将最后一次更新时的连通分量输出就行了
附上代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cassert>
using namespace std;
stack <
int>
S;
const int maxn = 1e5+
3;
int n, m, fir[maxn], nx[maxn], u[maxn], v[maxn], s, cnt, uu, vv, tot;
int dfn[maxn], low[maxn], Index, ans[maxn], Ans[maxn];
bool vis[maxn];
inline void addedge(
int fr,
int to) {
u[++cnt] =
fr;
v[cnt] =
to;
nx[cnt] =
fir[fr];
fir[fr] =
cnt;
}
inline void Tarjan(
int x) {
dfn[x] = low[x] = ++
Index;
vis[x] =
1;
S.push(x);
int k =
fir[x];
while (k != -
1) {
if(!
dfn[v[k]]) {
Tarjan(v[k]);
low[x] =
min(low[x], low[v[k]]);
}
else if(vis[v[k]])
low[x] =
min(low[x], dfn[v[k]]);
k =
nx[k];
}
if(low[x] ==
dfn[x]) {
int tot =
0;
while (!
S.empty()) {
k =
S.top();
vis[k] =
0;
S.pop();
Ans[++tot] =
k;
if(x == k)
break;
}
if(tot >= ans[
0]) {
for(
int i=
1; i<=tot; i++
) {
ans[i] =
Ans[i];
}
ans[0] =
tot;
}
}
}
int main() {
scanf("%d%d", &n, &
m);
memset(fir, -
1,
sizeof(fir));
for(
int i=
1; i<=m; i++
) {
scanf("%d%d%d", &uu, &vv, &
s);
if(s ==
1) addedge(uu, vv);
else addedge(uu, vv), addedge(vv, uu);
}
for(
int i=
1; i<=n; i++
) {
if(!
dfn[i]) Tarjan(i);
}
sort(ans+
1, ans+
1+ans[
0]);
printf("%d\n", ans[
0]);
for(
int i=
1; i<=ans[
0]; i++) printf(
"%d ", ans[i]);
return 0;
}
转载于:https://www.cnblogs.com/bljfy/p/9439224.html
相关资源：2016秋人音版音乐五上第3课《丰收锣鼓》ppt课件1
