CODEVS 1332 上白澤慧音

2019-11-11 01:36:30

字體：大中小

供稿：網(wǎng)友

題目描述

在幻想鄉(xiāng)，上白澤慧音是以知識淵博聞名的老師。春雪異變導致人間之里的很多道路都被大雪堵塞，使有的學生不能順利地到達慧音所在的村莊。因此慧音決定換一個能夠聚集最多人數(shù)的村莊作為新的教學地點。人間之里由N個村莊（編號為1..N）和M條道路組成，道路分為兩種一種為單向通行的，一種為雙向通行的，分別用1和2來標記。如果存在由村莊A到達村莊B的通路，那么我們認為可以從村莊A到達村莊B，記為(A,B)。當(A,B)和(B,A)同時滿足時，我們認為A,B是絕對連通的，記為<A,B>。絕對連通區(qū)域是指一個村莊的集合，在這個集合中任意兩個村莊X,Y都滿足<X,Y>?，F(xiàn)在你的任務是，找出最大的絕對連通區(qū)域，并將這個絕對連通區(qū)域的村莊按編號依次輸出。若存在兩個最大的，輸出字典序最小的，比如當存在1,3,4和2,5,6這兩個最大連通區(qū)域時，輸出的是1,3,4。

輸入描述

第1行：兩個正整數(shù)N,M

第2..M+1行：每行三個正整數(shù)a,b,t, t = 1表示存在從村莊a到b的單向道路，t = 2表示村莊a,b之間存在雙向通行的道路。保證每條道路只出現(xiàn)一次。

輸出描述

第1行： 1個整數(shù)，表示最大的絕對連通區(qū)域包含的村莊個數(shù)。

第2行：若干個整數(shù)，依次輸出最大的絕對連通區(qū)域所包含的村莊編號。

樣例輸入

5 5

1 2 1

1 3 2

2 4 2

5 1 2

3 5 1

樣例輸出

1 3 5

數(shù)據(jù)范圍及提示

對于60%的數(shù)據(jù)：N <= 200且M <= 10,000

對于100%的數(shù)據(jù)：N <= 5,000且M <= 50,000

分析

tarjan的裸題，但是要稍微記錄一下當前強聯(lián)通分量是由哪些組成的，而且有多長，其實在做的時候染一下色就好了。

代碼

#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; }