Cod sursa(job #1702717)

Utilizator refugiatBoni Daniel Stefan refugiat Data 15 mai 2016 14:46:42
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
ifstream si("ctc.in");
ofstream so("ctc.out");
const int NMAX=100005;
vector<int> v[NMAX];
vector<int> x[NMAX];
bitset<NMAX> viz;
stack<int> q;
vector<int>sol[NMAX];
int cont=0;
void dfs1(int poz)
{
    //cout<<poz<<' ';
    int i;
    viz[poz]=1;
    int n;
    n=v[poz].size();
    for(i=0;i<n;++i)
    {
        if(!viz[v[poz][i]])
        {
            dfs1(v[poz][i]);
        }
    }
    q.push(poz);
}
void dfs2(int poz)
{
    //cout<<poz<<' ';
    int i;
    viz[poz]=0;
    int n;
    n=x[poz].size();

    sol[cont].push_back(poz);
    for(i=0;i<n;++i)
    {
        if(viz[x[poz][i]])
        {
            dfs2(x[poz][i]);
        }
    }
}
int main()
{
    int n,m;
    si>>n>>m;
    int i,a,b;
    for(i=0;i<m;++i)
    {
        si>>a>>b;
        v[a].push_back(b);
        x[b].push_back(a);
    }
    for(i=1;i<=n;++i)
    {
        if(!viz[i])
        {
            dfs1(i);
        }
    }
    while(!q.empty())
    {
        if(viz[q.top()])
        {
            dfs2(q.top());
            ++cont;
            //cout<<'\n';
        }
        q.pop();
    }
    so<<cont<<'\n';
    int j;
    for(i=0;i<cont;++i)
    {
        m=sol[i].size();
        for(j=0;j<m;++j)
            so<<sol[i][j]<<' ';
        so<<'\n';
    }
    so.close();
    return 0;
}