Cod sursa(job #2649905)

Utilizator razviii237Uzum Razvan razviii237 Data 16 septembrie 2020 19:10:55
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 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;
bool pls[maxn], mns[maxn], done[maxn];

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

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

void dfsm (int x) {
    mns[x] = true;
    if(pls[x] == true) { ans[k].push_back(x); done[x] = true; }
    for(auto u : tr[x]) {
        if(mns[u] == false) {
            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;
            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;
}