社区讨论

求助

B3609[图论与代数结构 701] 强连通分量参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo2egyrc
此快照首次捕获于
2023/10/23 12:31
2 年前
此快照最后确认于
2023/11/03 13:17
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10;
inline int read(){
    int sum=0,check=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-'){
        	check=-1;
		}
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        sum=(sum<<1)+(sum<<3)+(ch^48);
        ch=getchar();
    }
    return sum*check;
}
int n,m;
int cnt,Time,len,CNT;
int root[N],flag[N];
int head[N],dfn[N],low[N],Stack[N];
bool instack[N];
vector<int> ans[N];
struct node{
	int to,next;
}edge[10*N];
void addedge(int from,int to){
	cnt++;
	edge[cnt].to=from;
	edge[cnt].next=head[from];
	head[from]=cnt;
}	
void tarjan(int n){
	dfn[n]=low[n]=++Time;
	Stack[++len]=n;
	instack[n]=true;
	for(int i=head[n];i;i=edge[i].next){
		int temp=edge[i].to;
		if(!dfn[temp]){
			tarjan(temp);
			low[n]=min(low[n],low[temp]);
		}
		else if(instack[temp]){
			low[n]=min(low[n],low[temp]);
		}
	}
	if(dfn[n]==low[n]){
		CNT++;
		while(len>0){
			int temp=Stack[len];
			len--;
			instack[temp]=false;
			ans[CNT].push_back(temp);
			root[temp]=CNT;
			if(temp==n){
				break;
			}
		}
	}
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int temp1=read(),temp2=read();
		addedge(temp1,temp2);	
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	printf("%lld\n",CNT);
	for(int i=1;i<=CNT;i++){
		sort(ans[i].begin(),ans[i].end());
	}
	for(int i=1;i<=n;i++){
		if(flag[root[i]]){
			continue;
		}
		flag[root[i]]=true;
		for(int j=0;j<ans[root[i]].size();j++){
			printf("%lld ",ans[root[i]][j]);
		}
		printf("\n");
	}
	return 0;
}

全错样例都过不了

回复

3 条回复,欢迎继续交流。

正在加载回复...