Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector < int > G[128], GT[128], CTC[128];
- int n, m, x, y, viz[128], nr;
- stack < int > S;
- void read () {
- cin >> n >> m;
- while (m --) {
- cin >> x >> y;
- G[x].push_back (y);
- GT[y].push_back (x);
- }
- }
- void DFSP (int Nod) {
- viz[Nod] = 1;
- for (unsigned int i = 0; i < G[Nod].size(); ++i) {
- int vecin = G[Nod][i];
- if (!viz[vecin]) DFSP(vecin);
- }
- S.push (Nod);
- }
- void DFSM (int Nod) {
- viz[Nod] = 2;
- CTC[nr].push_back (Nod);
- for (unsigned int i = 0; i < GT[Nod].size(); ++i) {
- int vecin = GT[Nod][i];
- if (viz[vecin] == 1) DFSM (vecin);
- }
- }
- void solve () {
- for (int i = 1; i <= n; ++i) if (!viz[i]) DFSP(i);
- while (!S.empty()) {
- int Nod = S.top();
- S.pop();
- if (viz[Nod] == 1) {
- nr ++;
- DFSM(Nod);
- }
- }
- }
- void print () {
- }
- int main() {
- read();
- solve();
- print();
- return 0;
- }
Add Comment
Please, Sign In to add comment