1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| #include<bits/stdc++.h> using namespace std; #define Debug(x) cout<<#x<<':'<<x<<endl #define INF 0x7fffffff typedef long long ll; typedef pair<ll,ll> P; const ll maxn=1e2+11; struct Edge{ ll to,nx; }e[maxn]; ll head[maxn],vis[maxn],path[maxn][maxn]; ll n,m,tmp,root; void add(ll u,ll v){ e[tmp]={v,head[u]};head[u]=tmp++; } void dfs(ll u){ vis[u]=1; for(ll i=head[u];i;i=e[i].nx){ ll v=e[i].to; if(!vis[v]){ path[root][v]=1; dfs(v); } } } void solve(){ for(root=0;root<n;root++){ memset(vis,0,sizeof(vis)); dfs(root); } for(ll i=0;i<n;i++){ for(ll j=0;j<n;j++) if(path[i][j]==1 && path[j][i]==1){ cout<<"NO"<<endl;return ; } } cout<<"YES"<<endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); while(cin>>n && n){ memset(head,0,sizeof(head));tmp=1; memset(path,0,sizeof(path)); cin>>m; for(ll i=1;i<=m;i++){ ll u,v;cin>>u>>v;add(u,v); } solve(); } return 0; }
|