Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int n, m; // число вершин
- vector<int> g[101]; // граф
- bool used[101], r = false;
- vector<int> ans, cl;
- bool dfs (int v) {
- if(cl[v] == 1){ return true; }
- if(cl[v] == 2){ return false; }
- cl[v] = 1;
- used[v] = true;
- for (size_t i=0; i<g[v].size(); ++i) {
- int to = g[v][i];
- // cout <<to <<' ';
- if (dfs(to)){
- return true;
- }
- }
- ans.push_back (v);
- cl[v] = 2;
- return false;
- }
- /*bool dfs (int v, int s) {
- cl[v] = 1;
- for (size_t i = 0; i < g[v].size(); i++) {
- int to = g[v][i];
- if (cl[to] == 0 && to != v && to != s) {
- if (dfs (to, v)) return true;
- }
- else if (cl[to] == 1 && to != v && to != s) {
- return true;
- }
- }
- ans.push_back(v);
- cl[v] = 2;
- return false;
- }*/
- void topological_sort() {
- for (int i=0; i<n; ++i)
- used[i] = false;
- ans.clear();
- for (int i=0; i<n; ++i)
- if (!used[i]){
- //cout <<i <<' ';
- if(dfs(i)){
- r = true;
- }
- }
- reverse (ans.begin(), ans.end());
- if(!r){
- cout <<"Yes" <<endl;
- for(int i = 0; i < n; i++){
- cout <<ans[i] + 1 <<' ';
- }
- } else {
- cout <<"No";
- }
- /*if (!used[0])
- dfs (0);
- bool t = true;
- for(int i = 0; i < n; i++){
- if(!used[i]){cout <<i <<endl; t = false;}
- }
- if(t){
- cout <<"Yes" <<endl;
- reverse (ans.begin(), ans.end());
- for(int i = 0; i < n; i++){
- cout <<ans[i] <<' ';
- }
- } else {
- cout <<"No";
- }*/
- }
- int main(){
- cin >>n >>m;
- cl.assign(n, 0);
- for(int i = 0; i < m; i++){
- int x, y;
- cin >>x >>y;
- x--;
- y--;
- g[x].push_back(y);
- //cout <<g[x] <<' ' <<g[y] <<endl;
- }
- topological_sort();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement