又贡献了一版的WA和TLE一道题,本来不是很难,但是由于初始化有问题,一直RE。
先说说这道题的思路吧,两次dfs进行缩点,缩点之后再深搜一次找出最长路径与缩点之后的顶点数相比,
相等则输出Yes,否则输出No。
#include<iostream>
using namespace std;
struct node{
int v;
node *next;
};
node pp[6005],qq[6005];
node *dd[1005],*rd[1005];
bool mark[1005];
bool map[1005][1005];
int cal[1005];
int ret[1005];
int n,m,ti;
void init()
{
memset(mark,false,sizeof(mark));
memset(cal,0,sizeof(cal));
memset(dd,0,sizeof(dd));
memset(rd,0,sizeof(rd));
memset(ret,0,sizeof(ret));
memset(map,false,sizeof(map));
}
void input()
{
int u,v,i;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++){
scanf("%d%d",&u,&v);
pp[i].v=v;
pp[i].next=dd[u];
dd[u]=&pp[i];
qq[i].v=u;
qq[i].next=rd[v];
rd[v]=&qq[i];
}
}
void dfs(int k)
{
mark[k]=true;
node *p=dd[k];
while(p){
if(!mark[p->v])
dfs(p->v);
p=p->next;
}
cal[++ti]=k;
}
void rdfs(int k){
ret[k]=ti;
node *p=rd[k];
while(p){
if(!ret[p->v])
rdfs(p->v);
else if(ti!=ret[p->v]){
map[ti][ret[p->v]]=true;
}
p=p->next;
}
}
int dfsr(int k){
int ans=0;
for(int i=1;i<=ti;i++){
if(map[k][i]){
if(!cal[i])
dfsr(i);
ans=max(ans,cal[i]);
}
}
cal[k]=ans+1;
return cal[k];
}
int main()
{
int t,i;
scanf("%d",&t);
while(t--){
init();
input();
ti=0;
for(i=1;i<=n;i++)
if(!mark[i])
dfs(i);
for(ti=0,i=n;i>0;i--){
if(!ret[cal[i]]){
ti++;
rdfs(cal[i]);
}
}
int ans=0;
memset(cal,0,sizeof(cal));
for(i=1;i<=ti;i++){
if(!cal[i])
dfsr(i);
ans=max(ans,cal[i]);
}
if(ans==ti) printf("Yes\n");
else printf("No\n");
}
return 0;
}