C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2020-01-05 17:34:52

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 128;

int N;
vector<int> G[MAXN];
vector<int> rG[MAXN];
bool vis[MAXN];
int scc[MAXN];
int scc_cnt;
vector<int> path;

vector<int> g[MAXN];
int indeg[MAXN];
int outdeg[MAXN];

void dfs(int s) {
  vis[s] = true;
  for (auto t: G[s]) if (!vis[t]) dfs(t);
  path.push_back(s);
}

void rdfs(int s) {
  scc[s] = scc_cnt;
  for (auto t: rG[s]) if (!scc[t]) rdfs(t);
}

void Kosaraju() {
  for (int i = 1; i <= N; i++) if (!vis[i]) dfs(i);
  reverse(path.begin(), path.end());
  for (auto i: path) if (!scc[i]) scc_cnt++, rdfs(i);
}

int main() {
  cin >> N;
  for (int s = 1; s <= N; s++) {
    int t;
    while (cin >> t && t) G[s].push_back(t), rG[t].push_back(s);
  }
  Kosaraju();
  for (int s = 1; s <= N; s++) {
    for (auto t: G[s]) if (scc[s] != scc[t]) g[scc[s]].push_back(scc[t]);
  }
  // for (int s = 1; s <= N; s++) cout << scc[s] << " "; cout << endl;
  for (auto s = 1; s <= scc_cnt; s++) {
    for (auto t: g[s]) indeg[t]++;
    for (auto t: g[s]) outdeg[s]++;
  }
  int ans_a = count(indeg+1, indeg+scc_cnt+1, 0);
  int ans_b = scc_cnt == 1? 0: max(int(count(outdeg+1, outdeg+scc_cnt+1, 0)), ans_a);
  cout << ans_a << endl;
  cout << ans_b << endl;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 428K, 提交时间: 2022-02-15 21:06:32

#include<bits/stdc++.h>
using namespace std;
int n,s[101],d,group[101],cnt;
bool vis[101],in[101],out[101];
vector <int> g[2][101];
void kosaraju(const int &x){
	vis[x] = 1;
	for (int i = 0;i < g[0][x].size();i++)
		if (!vis[g[0][x][i]])
			kosaraju(g[0][x][i]);
	s[++d] = x;
}
void rkosaraju(const int &x){
	group[x] = cnt;
	vis[x] = 0;
	for (int i = 0;i < g[1][x].size();i++)
		if (vis[g[1][x][i]])
			rkosaraju(g[1][x][i]);
}
int main(){
	cin>>n;
	int x,y,i,j;
	for (i = 1;i <= n;i++)
		while (cin>>x){
			if (!x)break;
			g[0][i].push_back(x);
			g[1][x].push_back(i);
		}
	for (i = 1;i <= n;i++)
		if (!vis[i])
			kosaraju(i);
	for (i = d;i;i--)
		if (vis[s[i]]){
			cnt++;
			rkosaraju(s[i]);
		}
	for (i = 1;i <= n;i++)
		for (j = 0;j < g[0][i].size();j++)
			if (group[i] != group[g[0][i][j]]){
				in[group[g[0][i][j]]] = 1;
				out[group[i]] = 1;
			}
	if (cnt == 1){
		cout<<"1\n0";
		return 0;
	}
	x = 0;
	y = 0;
	for (i = 1;i <= cnt;i++){
		if (!in[i])x++;
		if (!out[i])y++;
	}
	cout<<x<<endl<<max(x,y);
	return 0;
}