点击打开链接
题意：中文
思路：思路就是当前已经走过的点，则将所有的需要这个点的边全部走一遍，这样的话复杂度就比较低了
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3fll; const int maxn=50010; int head1[maxn],head2[maxn],k1,k2; struct edge{ int x,y,next; }; edge E[maxn*2],EE[maxn*2]; void add_edge1(int u,int v,int w){ E[k1].x=v;E[k1].y=w;E[k1].next=head1[u];head1[u]=k1++; } void add_edge2(int u,int v,int w){ EE[k2].x=v;EE[k2].y=w;EE[k2].next=head2[u];head2[u]=k2++; } bool vis[maxn]; void dfs(int x){ vis[x]=1; for(int i=head2[x];i!=-1;i=EE[i].next){ if(vis[EE[i].x]&&!vis[EE[i].y]) dfs(EE[i].y); if(!vis[EE[i].x]&&vis[EE[i].y]) dfs(EE[i].x); } for(int i=head1[x];i!=-1;i=E[i].next){ if(vis[E[i].y]&&!vis[E[i].x]) dfs(E[i].x); } } int main(){ int N,J,M,u,v,c; scanf("%d%d%d",&N,&J,&M); memset(head1,-1,sizeof(head1)); memset(head2,-1,sizeof(head2)); k1=k2=0; for(int i=0;i<M;i++){ scanf("%d%d%d",&u,&v,&c); add_edge1(u,v,c);add_edge1(v,u,c); add_edge2(c,u,v); } dfs(J); for(int i=1;i<=N;i++){ printf("%d:",i); if(vis[i]) printf("Yes\n"); else printf("No\n"); } return 0; }