二次联通门 :
/* luogu P1726 上白泽慧音 Tarjan求强连通分量 输出最大强联通分量是什么 */#include#include #include #define Max 5020#define INF 1e7void read (int &now){ now = 0; char word = getchar (); while (word > '9' || word < '0') word = getchar (); while (word >= '0' && word <= '9') { now = now * 10 + word - '0'; word = getchar (); }}struct Edge{ int to; int next;}; int Count;int Saber; std :: stack Stack;struct Road{ int edge[Max]; int Count; };Road road[Max];Edge edge[Max << 6]; int Edge_Count;int edge_list[Max]; inline void AddEdge (int from, int to){ Edge_Count++; edge[Edge_Count].to = to; edge[Edge_Count].next = edge_list[from]; edge_list[from] = Edge_Count;} int father[Max];int low[Max];int ruri[Max];void Dfs (int now){ father[now] = ++Count; low[now] = Count; Stack.push (now); for (int i = edge_list[now]; i; i = edge[i].next) if (!father[edge[i].to]) { Dfs (edge[i].to); low[now] = low[edge[i].to] < low[now] ? low[edge[i].to] : low[now]; } else if (!ruri[edge[i].to]) low[now] = father[edge[i].to] < low[now] ? father[edge[i].to] : low[now]; int x; if (low[now] == father[now]) { Saber++; x = now + 1; while (x != now) { x = Stack.top (); Stack.pop (); ruri[x] = Saber; road[Saber].edge[++road[Saber].Count] = x; } }}int N, M;int main (int argc, char *argv[]){ read (N); read (M); int x, y; int type; int Max_Number = 0; int Min_Edge; for (register int i = 1; i <= M; i++) { read (x); read (y); read (type); AddEdge (x, y); if (type == 2) AddEdge (y, x); } int Answer_Count; for (int i = 1; i <= N; i++) if (!father[i]) Dfs (i); for (int i = 1; i <= Saber; i++) std :: sort (road[i].edge + 1, road[i].edge + 1 + road[i].Count); int pos; for (int i = 1; i <= Saber; i++) { if (road[i].Count > Max_Number) { Max_Number = road[i].Count; Min_Edge = road[i].edge[1]; pos = i; } else if (road[i].edge[1] < Min_Edge && road[i].Count == Max_Number) { Min_Edge = road[i].edge[1]; pos = i; } } printf ("%d\n", road[pos].Count); for (int i = 1; i <= road[pos].Count; i++) printf ("%d ", road[pos].edge[i]); return 0;}