求助
查看原帖
求助
733367
Anatomix楼主2023/6/23 11:30
#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;
}

全错样例都过不了

2023/6/23 11:30
加载中...