本文共 1749 字，大约阅读时间需要 5 分钟。
给一个图，求最少需要几条边将其连成一个强连通图
tarjan，缩点，考虑缩点后的图，出度为0的点和入度为0的点，而所需要的边就是出度为0，和入度为0的点的较大值。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 2e4+10;vector G[MAXN];stack St;int Dfn[MAXN], Low[MAXN];int Vis[MAXN], Dis[MAXN][2]; // 0:in, 1:outint Fa[MAXN];int n, m;int times, cnt;void Init(){ for (int i = 1;i <= n;i++) G[i].clear(), Fa[i] = i; memset(Dfn, 0, sizeof(Dfn)); memset(Low, 0, sizeof(Low)); memset(Vis, 0, sizeof(Vis)); memset(Dis, 0, sizeof(Dis)); times = cnt = 0;}void Tarjan(int x){ St.push(x); Vis[x] = 1; Dfn[x] = Low[x] = ++times; for (int i = 0;i < G[x].size();i++) { int node = G[x][i]; if (Dfn[node] == 0) { Tarjan(node); Low[x] = min(Low[x], Low[node]); } else if (Vis[node] == 1) Low[x] = min(Low[x], Dfn[node]); } if (Low[x] == Dfn[x]) { ++cnt; while (x != St.top()) { Fa[St.top()] = cnt; Vis[St.top()] = 0; St.pop(); } Fa[St.top()] = cnt; Vis[St.top()] = 0; St.pop(); }}int main(){ int t; cin >> t; while (t--) { cin >> n >> m; Init(); int l, r; for (int i = 1;i <= m;i++) { cin >> l >> r; G[l].push_back(r); } for (int i = 1;i <= n;++i) if (!Dfn[i]) Tarjan(i); if (cnt == 1) cout << 0 << endl; else { for (int i = 1;i <= n;i++) { for (int j = 0;j < G[i].size();j++) { int node = G[i][j]; if (Fa[i] != Fa[node]) ++Dis[Fa[i]][1], ++Dis[Fa[node]][0]; } } int in = 0, out = 0; for (int i = 1;i <= cnt;i++) { if (Dis[i][0] == 0) in++; if (Dis[i][1] == 0) out++; } cout << max(out, in) << endl; } } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10821269.html