Anatomix @ 2023-06-23 11:30:06
#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;
}
全错样例都过不了
by technopolis_2085 @ 2023-06-23 11:40:34
建边建错了。
edge[cnt].to=from;
应该改为:
edge[cnt].to=to;
by technopolis_2085 @ 2023-06-23 11:42:27
试过了,改完了就可以AC。
by Anatomix @ 2023-06-23 11:44:27
@past_tense 感谢大佬 关注已点