Cod sursa(job #2092374)

Utilizator refugiatBoni Daniel Stefan refugiat Data 21 decembrie 2017 16:27:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#define NMAX 100005
using namespace std;
ifstream si("ctc.in");
ofstream so("ctc.out");
vector<int> v[NMAX];
vector<int> x[NMAX];
bitset<NMAX> viz;
stack<int> ord;
vector<int> sol[NMAX];
int cont=0;
void dfs1(int poz)
{
    viz[poz]=1;
    int n=v[poz].size();
    for(int i=0;i<n;++i)
    {
        if(!viz[v[poz][i]])
        {
            dfs1(v[poz][i]);
        }
    }
    ord.push(poz);
}
void dfs2(int poz)
{
    viz[poz]=0;
    int n=x[poz].size();
    for(int i=0;i<n;++i)
    {
        if(viz[x[poz][i]])
        {
            dfs2(x[poz][i]);
        }
    }
    sol[cont].push_back(poz);
}
int main()
{
    int n,m;
    si>>n>>m;
    int a,b;
    for(int i=0;i<m;++i)
    {
        si>>a>>b;
        v[a].push_back(b);
        x[b].push_back(a);
    }
    for(int i=1;i<=n;++i)
    {
        if(!viz[i])
        {
            dfs1(i);
        }
    }
    while(!ord.empty())
    {
        if(viz[ord.top()])
        {
            dfs2(ord.top());
            ++cont;
        }
        ord.pop();
    }
    so<<cont<<'\n';
    for(int i=0;i<cont;++i)
    {
        n=sol[i].size();
        for(m=0;m<n;++m)
            so<<sol[i][m]<<' ';
        so<<'\n';
    }
    return 0;
}