Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int color[100001];
- vector <int> g[100001];
- bool cycle=false;
- void dfs(int u){
- if(color[u]==1) {
- cycle=true;
- return ;
- }
- if(color[u]==2){
- return ;
- }
- color[u]=1;
- for(auto v:g[u]){
- dfs(v);
- }
- color[u]=2;
- }
- int main(){
- int n,m;
- scanf("%d %d",&n,&m);
- int head[n+1];
- vector <int> parent[n+1];
- for(int i=0;i<=n;i++){
- head[i]=0;
- }
- for(int i=1;i<=m;i++){
- int u,v;
- scanf("%d %d",&u,&v);
- g[v].push_back(u);
- parent[u].push_back(v);
- head[u]++;
- }
- for(int i=1;i<=n;i++){
- if(color[i]==0){
- dfs(i);
- if(cycle){
- printf("No");
- return 0;
- }
- }
- }
- printf("Yes\n");
- queue <int> q;
- vector <bool> visited(n+1,false);
- for(int i=1;i<=n;i++){//head[i]=0;
- if(head[i]==0) q.push(i);
- }
- while(!q.empty()){
- int u;
- u=q.front();
- q.pop();
- if(visited[u]) continue;
- bool con=true;
- for(auto pr:parent[u]){
- if(!visited[pr]) con=false;
- }
- if(con==false) continue;
- visited[u]=true;
- printf("%d ",u);
- for(auto v:g[u]){
- if(!visited[v]) {
- q.push(v);
- }
- }
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment