19pts求助
  • 板块P2835 刻录光盘
  • 楼主thrX
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/15 16:12
  • 上次更新2024/10/15 16:13:22
查看原帖
19pts求助
710862
thrX楼主2024/10/15 16:12
#include<bits/stdc++.h>
using namespace std;
const int maxn=222;
int n;
vector<int> e[maxn];
int dfn[maxn],low[maxn],stk[maxn],co[maxn],num,col,top;
void tarjan(int u){
	dfn[u]=low[u]=++num;
	stk[++top]=u;
	for(auto v:e[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(!co[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		co[u]=++col;
		while(stk[top]!=u){
			co[stk[top]]=col;
			top--;
		}
		top--;
	}
}
int main(){
	
	cin>>n;
	int v;
	for(int u=1;u<=n;u++){
		cin>>v;
		while(v!=0){
			e[u].push_back(v);
			cin>>v;
		}
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i);
	}
	cout<<col<<'\n';
	
	return 0;
}

使用tarjan强连通分量算法,个人认为题意就是求有多少个强连通分量

但是只有19pts

求条,玄关

2024/10/15 16:12
加载中...