Cod sursa(job #2649908)

Utilizator razviii237Uzum Razvan razviii237 Data 16 septembrie 2020 19:14:34
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

const int maxn = 1e5+5;

int n, m, x, y, k, bn;
int pls[maxn], mns[maxn];
bool done[maxn];

vector <int> nod[maxn], tr[maxn], ans[maxn];

void dfsp (int x) {
    pls[x] = bn;
    for(auto u : nod[x]) {
        if(pls[u] != bn) {
            dfsp(u);
        }
    }
}

void dfsm (int x) {
    mns[x] = bn;
    if(pls[x] == bn) { ans[k].push_back(x); done[x] = true; }
    for(auto u : tr[x]) {
        if(mns[u] != bn) {
            dfsm(u);
        }
    }
}

void check(int x) {
    //memset(pls, false, sizeof(pls));
    //memset(mns, false, sizeof(mns));
    dfsp(x);
    dfsm(x);
}

int main()
{
    int i;
    f >> n >> m;
    for(i = 1; i <= m; i ++) {
        f >> x >> y;
        nod[x].push_back(y);
        tr[y].push_back(x);
    }
    for(i = 1; i <= n; i ++) {
        if(done[i] == false) {
            ++k;
            bn++;
            check(i);
        }
    }

    g << k << '\n';
    for(i = 1; i <= k; i ++) {
        for(auto u : ans[i]) {
            g << u << ' ';
        }
        g << '\n';
    }

    f.close(); g.close();
    return 0;
}