Cod sursa(job #2503798)

Utilizator toadehuPuscasu Razvan Stefan toadehu Data 3 decembrie 2019 19:39:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;

int n,m,answ;

vector<int>nod1[100009],ans[100009];

vector<int>nod2[100009];

vector<int>ordine;

bool viz[100009];

void dfs1(int s)
{
    viz[s]=1;
    for(auto it : nod1[s])
    {
        if(viz[it]==0)
            dfs1(it);
    }
    ordine.push_back(s);
}


void dfs2(int s)
{
    ans[answ].push_back(s);
    viz[s]=1;
    for(auto it : nod2[s])
    {
        if(viz[it]==0)
        {
            dfs2(it);
        }
    }
}

int32_t main()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x,y;
        fin>>x>>y;
        nod1[x].push_back(y);
        nod2[y].push_back(x);
    }
    for(int i=1; i<=n; ++i)
    {
        if(!viz[i])
        {
            dfs1(i);
        }
    }
    memset(viz,0,sizeof(viz));
    for(int i=ordine.size()-1; i>=0; --i)
    {
        if(!viz[ordine[i]])
        {
            answ++;
            dfs2(ordine[i]);
        }
    }
    fout<<answ<<"\n";
    for(int i=1; i<=answ; ++i)
    {
        for(auto it:ans[i])
        {
            fout<<it<<" ";
        }
        fout<<"\n";
    }
}