Cod sursa(job #1366071)

Utilizator bianncaPoenar Bianca biannca Data 28 februarie 2015 18:53:56
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
//#include <iostream>
#include<fstream>
#include<vector>
#define mx 100001
using namespace std;
ifstream fin("ctc.in");
ofstream gout("ctc.out");
vector<int> v1[mx],v2[mx],so[mx];
bool viz[mx];
int n,m,nr,cnt,p[mx];
void citire()
{
    int i,x,y;
    fin>>n>>m;
    //viz.resize(n+1);
    for(i=1;i<=m;++i)
    {

        fin>>x>>y;
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
    fin.close();
}
void dfs(int s)
{
    viz[s]=true;
    for(unsigned int i=0;i<v1[s].size();++i)
        if(!viz[v1[s][i]])
    dfs(v1[s][i]);

    cnt++;
    p[cnt]=s;
    p[cnt]=s;
}
void dfst(int s)
{
    viz[s]=false;
    so[nr].push_back(s);//nr-numar comp; so-v solutie
    for(unsigned int i=0;i<v2[s].size();++i)
        {
            if(viz[v2[s][i]])
        dfst(v2[s][i]);
    }
}
int main()
{
    int i;
    citire();
    for(i=1;i<=n;++i)
        if(!viz[i])
        dfs(i);

    for(i=n;i>=1;--i)
    {
        if(viz[p[i]])
    {
        nr++;
        dfst(p[i]);}
    }
    gout<<nr<<'\n';
    for(i=1;i<=nr;++i)
    {
        for(unsigned int j=0;j<so[i].size();++j)
            gout<<so[i][j]<<" ";
        gout<<'\n';
    }

gout.close();
    return 0;
}