不知道为啥RE,下了一组数据如下
输入:
5
2 4 3 0
4 5 0
0
0
1 0
输出:
1
2
我的输出:不输出
挑灯夜战萌新已经快疯,恳请大佬帮我。
测试信息: 测试信息
附上有注释的代码:
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define MAXN 5000005
using namespace std;
int n;
vector<int> oldG[MAXN]; //老G是原图
vector<int> G[MAXN]; //缩点之后的图
//强连通分量的变量们
int dfn[MAXN], low[MAXN];
int scccnt, scc[MAXN];
int sum;
stack<int> s;
int in[MAXN], out[MAXN]; //缩完点之后的图的每个点的出度和入度
int vis1[MAXN], vis2[MAXN]; //分别标记这个点有没有被统计答案过(在最后面用了)
void tarjan(int u) {
dfn[u] = low[u] = ++sum;
s.push(u);
for (int i = 0; i < oldG[u].size(); ++i) {
int v = oldG[u][i];
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else {
if (!scc[v]) {
low[u] = min(low[u], low[v]);
}
}
}
if (dfn[u] == low[u]) { //形成强连通分量
scccnt++;
int v;
do {
v = s.top();
s.pop();
scc[v] = scccnt;
} while (v != u) ;
}
}
signed main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int v;
while (cin >> v) {
if (v == 0) {
break;
}
oldG[i].push_back(v);
}
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
tarjan(i);
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < oldG[i].size(); ++j) {
if (scc[i] != scc[ oldG[i][j] ]) {
G[scc[i]].push_back(scc[oldG[i][j]]);
in[ scc[G[i][j]] ] += 1;
out[scc[i]] += 1;
} //缩点之后建图
}
}
int ans1 = 0, ans2 = 0;
bool vis = 0;
for (int i = 2; i <= n; ++i) {
if (scc[i] != scc[i-1]) {
vis = 1;
break;
}
} //特判,如果只有一个强连通分量
if (vis == 0) {
cout << 1 << endl << 0 << endl;
return 0;
}
//正常统计出入度并输出答案
for (int i = 1; i <= n; ++i) {
if (!in[scc[i]] && !vis1[scc[i]]) ans1++, vis1[scc[i]] = 1;
if (!out[scc[i]] && !vis2[scc[i]]) ans2++, vis2[scc[i]] = 1;
}
cout << ans1 << endl << max(ans1, ans2) << endl;
return 0;
}
小菊弱感激不尽!!!