Cod sursa(job #2488212)

Utilizator Catalin_GriuGriu Catalin Catalin_Griu Data 6 noiembrie 2019 14:29:32
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <set>
#include <fstream>
#include <cstring>
#include <queue>
#include <array>
using namespace std;

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

int n, m;
vector <int> v[100004];
vector <int> v2[100004];
vector <vector<int>> ans;
int uz[100004];
queue<int> q;

void dfs(int nod){
    for(auto i:v[nod])
        if(!uz[i])
        {
            uz[i] = uz[nod]+1;
            dfs(i);
        }
    q.push(nod);
}

void dfs2(int nod){
    for(auto i:v[nod])
        if(!uz[i])
        {
            uz[i] = uz[nod]+1;
            dfs2(i);
        }
    ans.back().push_back(nod);
}

int main()
{
    fin>>n>>m;
    int a, b;
    for(int i=0; i<m; i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        v2[b].push_back(a);
    }
    for(int i=1; i<=n; i++)
    {
        if(!uz[i])
            dfs(i);
    }
    memset(uz, 0, sizeof(uz));
    while(!q.empty())
    {
        if(!uz[q.front()])
        {
            uz[q.front()]=1;
            ans.push_back(vector<int>());
            dfs2(q.front());

        }
            q.pop();

    }
    fout<<ans.size()<<'\n';
    for(auto i : ans)
    {
        for(auto j:i)
            fout<<j<< ' ';
        fout<<'\n';
    }




    return 0;
}