Cod sursa(job #2488583)

Utilizator EduardTudosaEduard Bogdan EduardTudosa Data 7 noiembrie 2019 09:30:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

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

int n , m , x , y , nrc;

vector <int> G1[100001];
vector <int> G2[100001];
vector <int> H;
vector < vector <int> > ans;
bool uz[100001];

void df1(int nod)
{
    uz[nod] = 1;
    for(vector <int> :: iterator it = G1[nod].begin() ; it != G1[nod].end() ; it ++)
    {
        if(uz[*it]) continue;
        df1(*it);
    }
    H.push_back(nod);
}

void df2(int nod)
{
    uz[nod] = 1;
    for(vector <int> :: iterator it = G2[nod].begin() ; it != G2[nod].end() ; it ++)
    {
        if(uz[*it]) continue;
        df2(*it);
    }
    ans.back().push_back(nod);
}

int main()
{
    fin >> n >> m;
    for(int i = 1 ; i <= m ; i ++)
    {
        fin >> x >> y;
        G1[x].push_back(y);
        G2[y].push_back(x);
    }
    for(int i = 1 ; i <= n ; i ++)
        if(!uz[i])
            df1(i);
    memset(uz , 0 , sizeof(uz));
    for(int i = H.size() - 1 ; i >= 0 ; i --)
        if(!uz[H[i]])
        {
            ans.push_back(vector <int>());
            df2(H[i]);
        }
    fout << ans.size() << '\n';
    for(int i = 0 ; i < int(ans.size()) ; i ++)
    {
        for(vector <int> :: iterator it = ans[i].begin() ; it != ans[i].end() ; it ++)
            fout << *it << ' ';
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}