題目描述
在幻想鄉(xiāng)，上白澤慧音是以知識(shí)淵博聞名的老師。春雪異變導(dǎo)致人間之里的很多道路都被大雪堵塞，使有的學(xué)生不能順利地到達(dá)慧音所在的村莊。因此慧音決定換一個(gè)能夠聚集最多人數(shù)的村莊作為新的教學(xué)地點(diǎn)。人間之里由N個(gè)村莊（編號(hào)為1..N）和M條道路組成，道路分為兩種一種為單向通行的，一種為雙向通行的，分別用1和2來標(biāo)記。如果存在由村莊A到達(dá)村莊B的通路，那么我們認(rèn)為可以從村莊A到達(dá)村莊B，記為(A,B)。當(dāng)(A,B)和(B,A)同時(shí)滿足時(shí)，我們認(rèn)為A,B是絕對(duì)連通的，記為<A,B>。絕對(duì)連通區(qū)域是指一個(gè)村莊的集合，在這個(gè)集合中任意兩個(gè)村莊X,Y都滿足<X,Y>?，F(xiàn)在你的任務(wù)是，找出最大的絕對(duì)連通區(qū)域，并將這個(gè)絕對(duì)連通區(qū)域的村莊按編號(hào)依次輸出。若存在兩個(gè)最大的，輸出字典序最小的，比如當(dāng)存在1,3,4和2,5,6這兩個(gè)最大連通區(qū)域時(shí)，輸出的是1,3,4。 輸入描述
第1行：兩個(gè)正整數(shù)N,M
第2..M+1行：每行三個(gè)正整數(shù)a,b,t, t = 1表示存在從村莊a到b的單向道路，t = 2表示村莊a,b之間存在雙向通行的道路。保證每條道路只出現(xiàn)一次。
輸出描述
第1行： 1個(gè)整數(shù)，表示最大的絕對(duì)連通區(qū)域包含的村莊個(gè)數(shù)。
第2行：若干個(gè)整數(shù)，依次輸出最大的絕對(duì)連通區(qū)域所包含的村莊編號(hào)。
樣例輸入
5 5
1 2 1
1 3 2
2 4 2
5 1 2
3 5 1
樣例輸出
3
1 3 5
數(shù)據(jù)范圍及提示
對(duì)于60%的數(shù)據(jù)：N <= 200且M <= 10,000
對(duì)于100%的數(shù)據(jù)：N <= 5,000且M <= 50,000
分析
tarjan的裸題，但是要稍微記錄一下當(dāng)前強(qiáng)聯(lián)通分量是由哪些組成的，而且有多長，其實(shí)在做的時(shí)候染一下色就好了。
代碼
#include <bits/stdc++.h>#define N 5010using namespace std;stack <int> S;vector <int> E[N];int dfn[N],low[N];int belone[N],num[N];int cnt = 0;int tot = 0;int ans = 0;int n,m;bool vis[N];void tarjan(int x){ low[x] = dfn[x] = cnt++; S.push(x); vis[x] = true; for (int i = 0; i < E[x].size(); i++) { int v = E[x][i]; if (!dfn[v]) { tarjan(v); low[x] = min(low[x],low[v]); } else if(vis[v]) low[x] = min(low[x],dfn[v]); } if (dfn[x] == low[x]) { belone[x] = ++cnt; num[cnt]++; while (true) { int now = S.top(); S.pop(); vis[now] = false; num[cnt]++; belone[now] = cnt; if(now == x) break; } }}int main(){ scanf("%d%d",&n,&m); for (int i = 1; i <= m; i++) { int k,x,y; scanf("%d%d%d",&x,&y,&k); E[x].push_back(y); if (k == 2) E[y].push_back(x); } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); int s; for (int i = 1; i <= n; i++) if (num[belone[i]] > ans) { ans = num[belone[i]]; s = i; }
