tarjan求縮點,然後算縮點之後的圖是不是一字鏈。
判斷是不是一字鏈很簡單,直接dfs求出一條最長邊。
看最長邊是不是等於縮點之後的數目即可。
#include#include #include #include #include #include #include #include using namespace std; #define maxm 10000 #define maxn 1100 #define eps 0.000001 #define zero(x) ((fabs(x) qq; void init() { memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); memset(shuyu,0,sizeof(shuyu)); memset(dnf,0,sizeof(dnf)); memset(low,0,sizeof(low)); memset(instack,0,sizeof(instack)); memset(viss,0,sizeof(viss)); while(!qq.empty())qq.pop(); num=0; nums=1; times=1; } void add(int u,int v) { edge[num].u=u; edge[num].v=v; edge[num].next=head[u]; head[u]=num++; } void tarjan(int x) { dnf[x]=low[x]=times++; instack[x]=1; qq.push(x); for(int i=head[x]; i!=-1; i=edge[i].next) { int y=edge[i].v; if(!dnf[y]) { tarjan(y); low[x]=min(low[x],low[y]); } else if(instack[y]) { low[x]=min(low[x],dnf[y]); } } if(low[x]==dnf[x]) { int y=-1; while(x!=y) { y=qq.top(); shuyu[y]=nums; qq.pop(); instack[y]=0; } nums++; } } void start() { for(int i=1; i<=n; i++) { if(!dnf[i])tarjan(i); } } int dfs(int x,int p) { int mm=p; for(int i=head[x]; i!=-1; i=edge[i].next) { mm=max(mm,dfs(edge[i].v,p+1)); } return mm; } } G,g; int main() { int n,i,j,m,a,b,T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); G.init(); g.init(); G.n=n; for(i=1; i<=m; i++) { scanf("%d%d",&a,&b); G.add(a,b); } G.start(); g.n=G.nums; int nin,nout; nin=nout=0; for(i=1; i<=G.n; i++) { for(j=G.head[i]; j!=-1; j=G.edge[j].next) { int u=G.edge[j].u; int v=G.edge[j].v; if(G.shuyu[u]==G.shuyu[v])continue; G.id[G.shuyu[v]]++; G.od[G.shuyu[u]]++; // cout< 1||nout>1) { cout<<"No"<