Cod sursa(job #1366060)

Utilizator bianncaPoenar Bianca biannca Data 28 februarie 2015 18:41:07
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
//#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
#define mx 100001
using namespace std;
ifstream fin("ctc.in");
ofstream gout("ctc.out");
vector<int> v1[mx],v2[mx],so[mx];
queue<int> q;
vector<bool> viz;
int n,m,nr=0,cnt=0,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]);
    p[++cnt]=s;//retine nodurile de la care se poate ajunge pornind din s
}
void dfst(int s)
{
    viz[s]=false;
    for(unsigned int i=0;i<v2[s].size();++i)
        if(viz[v2[s][i]])
        dfst(v2[s][i]);
    so[nr].push_back(s);//retine toate nodurile de la care se poate ajunge in s
}

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();++i)
            gout<<so[i][j]<<" ";
        gout<<'\n';
    }


    return 0;
}