代码如下,我第一遍甚至都没在出栈是将 vis 数组变成 false ,结果都 A 了
第一遍
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct node{
int date,to,lt=0;//id
}e[N];
int chudu[N],n,m,sta[N],last[N],sum[N],low[N],dfn[N],num,vis[N],tot,sta_tot,l_sum,id[N];//id属于那个连通块,l_sum连通块数量
void add(int u,int v){
e[++tot].date=u;
e[tot].to=v;
e[tot].lt=last[u];
last[u]=tot;
return ;
}
void trajan(int u){//u表是从当前是哪个点
low[u]=dfn[u]=++num;
sta[++sta_tot]=u,vis[u]=true;//入栈
for(int i=last[u];i;i=e[i].lt){
int v=e[i].to;
if(!dfn[v]){//还未遍历过
trajan(v);
low[u]=min(low[u],low[v]);//能到的dfs序最小的点是哪个
}
else if(vis[v]){//在栈中,即两者在同一条链中,有父子关系
low[u]=min(low[u],dfn[v]);
}
}
int k;
if(low[u]==dfn[u]){//无法继续往上走,构成了一个强联通块
l_sum++;
do{
k=sta[sta_tot],sta_tot--;//出栈
id[k]=l_sum;
sum[l_sum]++;//第k个连通块有多少个元素
}while(u!=k);
}
}
int main(){
cin>>n>>m;
int a,b;
for(int i=1;i<=n;i++)vis[i]=false;
for(int i=1;i<=m;i++){
cin>>a>>b;
add(a,b);
}
for(int i=1;i<=n;i++){
if(!dfn[i])trajan(i);//搜一边 trajan
}
for(int i=1;i<=n;i++){
for(int j=last[i];j;j=e[j].lt){
if(id[i]!=id[e[j].to])chudu[id[i]]++;//出度
}
}
int p=0;//是哪个联通块
for(int i=1;i<=l_sum;i++){
if(chudu[i]==0){
if(p){//不止一个连通块出度为 1
cout<<0;
return 0;
}
else p=i;
}
}
cout<<sum[p];
return 0;
}
第二遍
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct node{
int date,to,lt=0;//id
}e[N];
int chudu[N],n,m,sta[N],last[N],sum[N],low[N],dfn[N],num,vis[N],tot,sta_tot,l_sum,id[N];//id属于那个连通块,l_sum连通块数量
void add(int u,int v){
e[++tot].date=u;
e[tot].to=v;
e[tot].lt=last[u];
last[u]=tot;
return ;
}
void trajan(int u){//u表是从当前是哪个点
low[u]=dfn[u]=++num;
sta[++sta_tot]=u,vis[u]=true;//入栈
for(int i=last[u];i;i=e[i].lt){
int v=e[i].to;
if(!dfn[v]){//还未遍历过
trajan(v);
low[u]=min(low[u],low[v]);//能到的dfs序最小的点是哪个
}
else if(vis[v]){//在栈中,即两者在同一条链中,有父子关系
low[u]=min(low[u],dfn[v]);
}
}
int k;
if(low[u]==dfn[u]){//无法继续往上走,构成了一个强联通块
l_sum++;
do{
k=sta[sta_tot],sta_tot--;//出栈
vis[k]=false;
id[k]=l_sum;
sum[l_sum]++;//第k个连通块有多少个元素
}while(u!=k);
}
}
int main(){
cin>>n>>m;
int a,b;
for(int i=1;i<=n;i++)vis[i]=false;
for(int i=1;i<=m;i++){
cin>>a>>b;
add(a,b);
}
for(int i=1;i<=n;i++){
if(!dfn[i])trajan(i);//搜一边 trajan
}
for(int i=1;i<=n;i++){
for(int j=last[i];j;j=e[j].lt){
if(id[i]!=id[e[j].to])chudu[id[i]]++;//出度
}
}
int p=0;//是哪个联通块
for(int i=1;i<=l_sum;i++){
if(chudu[i]==0){
if(p){//不止一个连通块出度为 1
cout<<0;
return 0;
}
else p=i;
}
}
cout<<sum[p];
return 0;
}