Cod sursa(job #2253291)

Utilizator AnDrEeA1915Monea Andreea AnDrEeA1915 Data 3 octombrie 2018 20:53:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
#define nmax 200000

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, x, y, k, nr, a[nmax], viz[nmax];
vector<int> graph[nmax], graf[nmax], sol[nmax];

void dfs1(int x) {
    viz[x] = 1;
    for(int i = 0; i < graph[x].size(); ++i)
        if(!viz[graph[x][i]])
           dfs1(graph[x][i]);
    a[++k] = x;
}

void dfs2(int x) {
    viz[x] = 1;
    for(int i = 0; i < graf[x].size(); ++i)
        if(!viz[graf[x][i]])
            dfs2(graf[x][i]);
    sol[nr].push_back(x);
}
int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        fin >> x >> y;
        graph[x].push_back(y);
        graf[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i)
        if(!viz[i])
            dfs1(i);

    for(int i = 1; i <= n; ++i)
        viz[i] = 0;

    for(int i = n; i >= 1; --i) {
        int x = a[i];
        if(!viz[x]) {
            nr++;
            dfs2(x);
        }
    }
    fout << nr << "\n";
    for(int i = 1; i <= nr; ++i) {
        for(int j = 0; j < sol[i].size(); j++)
            fout << sol[i][j] << " ";
        fout << "\n";
    }
    return 0;
}