#include <cstdio> #include <cstring> #include <cmath> #include <cassert> #include <iostream> #include <algorithm> #include <iterator> #include <string> #include <vector> #include <queue> #include <bitset> #include <utility> #include <stack> using namespace std; typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<VI> VVI; #define MP make_pair #define FOR(v,p,k) for(auto v=(p);v<=(k);++v) #define FORD(v,p,k) for(auto v=(p);v>=(k);--v) #define REP(i,n) for(auto i=0;i<(n);++i) #define VAR(v,i) __typeof(i) v=(i) #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i) #define PB push_back #define ST first #define ND second #define SIZE(x) (int)x.size() #define ALL(c) c.begin(),c.end() #define ODD(x) ((x)%2) #define EVEN(x) (!(ODD(x))) #define VERTEX_OUT_OF_GRAPH 9999999 // http://www-users.mat.umk.pl/~stencel/acm/algorytmika_praktyczna.pdf template <class V, class E> struct Graph { // Typ krawędzi (Ed) dziedziczy po typie zawierającym dodatkowe informacje // związane z krawędzią (E). Zawiera on również pole v, określające numer // wierzchołka, do którego prowadzi krawędź. Zaimplementowany konstruktor // pozwala na skrócenie zapisu wielu funkcji korzystających ze struktury grafu. struct Ed : E { int v; Ed(E p, int w) : E(p), v(w) { } }; // Typ wierzchołka (Ve) dziedziczy po typie zawierającym dodatkowe informacje // z nim związane (V) oraz po wektorze krawędzi. To drugie dziedziczenie może // wydawać się na pierwszy rzut oka stosunkowo dziwne, lecz jest ono przydatne - // umożliwia łatwe iterowanie po wszystkich krawędziach wychodzących z // wierzchołka v: FOREACH(it, g[v]) struct Ve : V, vector<Ed> { }; // Wektor wierzchołków w grafie vector<Ve> g; // Konstruktor grafu - przyjmuje jako parametr liczbę wierzchołków Graph(int n = 0) : g(n) { } // Funkcja dodająca do grafu nową krawędź skierowaną z wierzchołka b do e, // zawierającą dodatkowe informacje określone przez zmienną d. inline void EdgeD(int b, int e, E d = E()) { g[b].PB(Ed(d, e)); } vector<int> nonTrivialScc; int topo; // Funkcja wykonująca algorytm DFS z wierzchołka v i aktualizująca wartości // zmiennych t void TopoDfs(int v) { // Jeśli wierzchołek nie był odwiedzony, to należy go odwiedzić if (!g[v].t) { // Zaznacz wierzchołek jako odwiedzony g[v].t = 1; // Odwiedź wszystkie wierzchołki, do których prowadzi krawędź z v FOREACH(it, g[v]) TopoDfs(it->v); // Zaktualizuj wartość t przetwarzanego wierzchołka g[v].t = --topo; } } // Właściwa funkcja implementująca sortowanie topologiczne inline void TopoSort(int withoutVertex) { FOREACH(it, nonTrivialScc) g[*it].t = 0; topo = SIZE(g); g[withoutVertex].t = topo; // Odwiedź wszystkie wierzchołki w grafie FOREACH(it, nonTrivialScc) TopoDfs(*it); } // Funkcja sprawdzająca, czy dany graf skierowany jest acykliczny inline bool AcyclicD(int withoutVertex) { // Wyznacz sortowanie topologiczne TopoSort(withoutVertex); // Dla każdej krawędzi w grafie sprawdź, czy prowadzi ona od wierzchołka // wcześniejszego do wierzchołka późniejszego w porządku topologicznym topo = SIZE(g); FOREACH(node_it, nonTrivialScc) { auto it = g.begin() + *node_it; if (it->t != topo) FOREACH(it2, *it) if (it->t >= g[it2->v].t) return false; } return true; } // Zmienna nr w pierwszej fazie algorytmu używana jest do pamiętania czasu // odwiedzania wierzchołków, natomiast w drugiej fazie algorytmu do numerowania // silnie spójnych składowych int nr; // Funkcja rekurencyjna, przeszukująca poddrzewo wierzchołka v. Jest ona // używana do realizacji obu faz przeszukiwania DFS void SccSDfs(int v) { // Jeśli wierzchołek nie był odwiedzony, to go odwiedź if (g[v].t == -1) { g[v].t = nr; // Odwiedź wszystkie wierzchołki, do których prowadzi krawędź z v FOREACH(it, g[v]) SccSDfs(it->v); // Jeśli wykonywana jest pierwsza faza algorytmu, to ustaw zmienną t // wierzchołka na czas przetworzenia (odejmowanie wartości 3 gwarantuje // przydzielanie numerów poczynając od 0 wzwyż) if (nr < 0) g[v].t = -(--nr) - 3; } } // Właściwa funkcja, wykonująca wyznaczanie silnie spójnych składowych void SccS() { // Zbuduj graf transponowany gt oraz ustaw wartości zmiennych t // wierzchołków na -1 (nieodwiedzone) Graph<V, E> gt(SIZE(g)); REP(x, SIZE(g)) { g[x].t = gt.g[x].t = -1; FOREACH(it, g[x]) gt.EdgeD(it->v, x); } gt.nr = -2; nr = 0; VI v(SIZE(g)); // Wykonaj pierwszą fazę przeszukiwania w głąb na grafie transponowanym oraz // wypełnij wektor v numerami wierzchołków w kolejności rosnących czasów // przetworzenia DFS REP(x, SIZE(g)) { gt.SccSDfs(x); v[gt.g[x].t] = x; } // Wykonaj drugą fazę przeszukiwania w głąb na oryginalnym grafie. FORD(x, SIZE(g) - 1, 0) { SccSDfs(v[x]); nr++; } } }; struct VertexT { int t; }; struct EdgeT {}; int main() { int n, m, a , b; scanf("%d %d", &n, &m); Graph<VertexT, EdgeT> graph(n); REP(i, m) { scanf("%d %d", &a, &b); --a; --b; graph.EdgeD(a, b); } graph.SccS(); VVI sccToVertices(n); REP(i, n) { sccToVertices[graph.g[i].t].PB(i); } int nonTrivialScc = -1; REP(i, n) { if (sccToVertices[i].size() > 1) { if (nonTrivialScc != -1) { printf("0\n\n"); return 0; } nonTrivialScc = i; } } if (nonTrivialScc == -1) { printf("NIE\n"); return 0; } graph.nonTrivialScc = sccToVertices[nonTrivialScc]; FOREACH(it, graph.nonTrivialScc) { auto &neighs = graph.g[*it]; FORD(i, SIZE(neighs)-1, 0) { if (graph.g[neighs[i].v].t != nonTrivialScc) { swap(neighs[i],neighs.back()); neighs.pop_back(); } } } VI res; res.reserve(n); FOREACH(it, graph.nonTrivialScc) { if (graph.AcyclicD(*it)) { res.PB(*it); } } int res_size = SIZE(res); printf("%d\n", res_size); REP(i, res_size) { printf("%d%s", res[i]+1, (((i+1)==res_size) ? "" : " ")); } printf("\n"); return 0; }
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 | #include <cstdio> #include <cstring> #include <cmath> #include <cassert> #include <iostream> #include <algorithm> #include <iterator> #include <string> #include <vector> #include <queue> #include <bitset> #include <utility> #include <stack> using namespace std; typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<VI> VVI; #define MP make_pair #define FOR(v,p,k) for(auto v=(p);v<=(k);++v) #define FORD(v,p,k) for(auto v=(p);v>=(k);--v) #define REP(i,n) for(auto i=0;i<(n);++i) #define VAR(v,i) __typeof(i) v=(i) #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i) #define PB push_back #define ST first #define ND second #define SIZE(x) (int)x.size() #define ALL(c) c.begin(),c.end() #define ODD(x) ((x)%2) #define EVEN(x) (!(ODD(x))) #define VERTEX_OUT_OF_GRAPH 9999999 // http://www-users.mat.umk.pl/~stencel/acm/algorytmika_praktyczna.pdf template <class V, class E> struct Graph { // Typ krawędzi (Ed) dziedziczy po typie zawierającym dodatkowe informacje // związane z krawędzią (E). Zawiera on również pole v, określające numer // wierzchołka, do którego prowadzi krawędź. Zaimplementowany konstruktor // pozwala na skrócenie zapisu wielu funkcji korzystających ze struktury grafu. struct Ed : E { int v; Ed(E p, int w) : E(p), v(w) { } }; // Typ wierzchołka (Ve) dziedziczy po typie zawierającym dodatkowe informacje // z nim związane (V) oraz po wektorze krawędzi. To drugie dziedziczenie może // wydawać się na pierwszy rzut oka stosunkowo dziwne, lecz jest ono przydatne - // umożliwia łatwe iterowanie po wszystkich krawędziach wychodzących z // wierzchołka v: FOREACH(it, g[v]) struct Ve : V, vector<Ed> { }; // Wektor wierzchołków w grafie vector<Ve> g; // Konstruktor grafu - przyjmuje jako parametr liczbę wierzchołków Graph(int n = 0) : g(n) { } // Funkcja dodająca do grafu nową krawędź skierowaną z wierzchołka b do e, // zawierającą dodatkowe informacje określone przez zmienną d. inline void EdgeD(int b, int e, E d = E()) { g[b].PB(Ed(d, e)); } vector<int> nonTrivialScc; int topo; // Funkcja wykonująca algorytm DFS z wierzchołka v i aktualizująca wartości // zmiennych t void TopoDfs(int v) { // Jeśli wierzchołek nie był odwiedzony, to należy go odwiedzić if (!g[v].t) { // Zaznacz wierzchołek jako odwiedzony g[v].t = 1; // Odwiedź wszystkie wierzchołki, do których prowadzi krawędź z v FOREACH(it, g[v]) TopoDfs(it->v); // Zaktualizuj wartość t przetwarzanego wierzchołka g[v].t = --topo; } } // Właściwa funkcja implementująca sortowanie topologiczne inline void TopoSort(int withoutVertex) { FOREACH(it, nonTrivialScc) g[*it].t = 0; topo = SIZE(g); g[withoutVertex].t = topo; // Odwiedź wszystkie wierzchołki w grafie FOREACH(it, nonTrivialScc) TopoDfs(*it); } // Funkcja sprawdzająca, czy dany graf skierowany jest acykliczny inline bool AcyclicD(int withoutVertex) { // Wyznacz sortowanie topologiczne TopoSort(withoutVertex); // Dla każdej krawędzi w grafie sprawdź, czy prowadzi ona od wierzchołka // wcześniejszego do wierzchołka późniejszego w porządku topologicznym topo = SIZE(g); FOREACH(node_it, nonTrivialScc) { auto it = g.begin() + *node_it; if (it->t != topo) FOREACH(it2, *it) if (it->t >= g[it2->v].t) return false; } return true; } // Zmienna nr w pierwszej fazie algorytmu używana jest do pamiętania czasu // odwiedzania wierzchołków, natomiast w drugiej fazie algorytmu do numerowania // silnie spójnych składowych int nr; // Funkcja rekurencyjna, przeszukująca poddrzewo wierzchołka v. Jest ona // używana do realizacji obu faz przeszukiwania DFS void SccSDfs(int v) { // Jeśli wierzchołek nie był odwiedzony, to go odwiedź if (g[v].t == -1) { g[v].t = nr; // Odwiedź wszystkie wierzchołki, do których prowadzi krawędź z v FOREACH(it, g[v]) SccSDfs(it->v); // Jeśli wykonywana jest pierwsza faza algorytmu, to ustaw zmienną t // wierzchołka na czas przetworzenia (odejmowanie wartości 3 gwarantuje // przydzielanie numerów poczynając od 0 wzwyż) if (nr < 0) g[v].t = -(--nr) - 3; } } // Właściwa funkcja, wykonująca wyznaczanie silnie spójnych składowych void SccS() { // Zbuduj graf transponowany gt oraz ustaw wartości zmiennych t // wierzchołków na -1 (nieodwiedzone) Graph<V, E> gt(SIZE(g)); REP(x, SIZE(g)) { g[x].t = gt.g[x].t = -1; FOREACH(it, g[x]) gt.EdgeD(it->v, x); } gt.nr = -2; nr = 0; VI v(SIZE(g)); // Wykonaj pierwszą fazę przeszukiwania w głąb na grafie transponowanym oraz // wypełnij wektor v numerami wierzchołków w kolejności rosnących czasów // przetworzenia DFS REP(x, SIZE(g)) { gt.SccSDfs(x); v[gt.g[x].t] = x; } // Wykonaj drugą fazę przeszukiwania w głąb na oryginalnym grafie. FORD(x, SIZE(g) - 1, 0) { SccSDfs(v[x]); nr++; } } }; struct VertexT { int t; }; struct EdgeT {}; int main() { int n, m, a , b; scanf("%d %d", &n, &m); Graph<VertexT, EdgeT> graph(n); REP(i, m) { scanf("%d %d", &a, &b); --a; --b; graph.EdgeD(a, b); } graph.SccS(); VVI sccToVertices(n); REP(i, n) { sccToVertices[graph.g[i].t].PB(i); } int nonTrivialScc = -1; REP(i, n) { if (sccToVertices[i].size() > 1) { if (nonTrivialScc != -1) { printf("0\n\n"); return 0; } nonTrivialScc = i; } } if (nonTrivialScc == -1) { printf("NIE\n"); return 0; } graph.nonTrivialScc = sccToVertices[nonTrivialScc]; FOREACH(it, graph.nonTrivialScc) { auto &neighs = graph.g[*it]; FORD(i, SIZE(neighs)-1, 0) { if (graph.g[neighs[i].v].t != nonTrivialScc) { swap(neighs[i],neighs.back()); neighs.pop_back(); } } } VI res; res.reserve(n); FOREACH(it, graph.nonTrivialScc) { if (graph.AcyclicD(*it)) { res.PB(*it); } } int res_size = SIZE(res); printf("%d\n", res_size); REP(i, res_size) { printf("%d%s", res[i]+1, (((i+1)==res_size) ? "" : " ")); } printf("\n"); return 0; } |