Cod sursa(job #1361372)

Utilizator 0051David Sera 0051 Data 25 februarie 2015 20:54:21
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

#define MAX 100010

typedef vector < int > ::iterator iter;
vector < int > g[MAX];
vector < int > v[MAX];
vector < int > s[MAX];
int n,m,k,dr,st[MAX];
bool viz[MAX];

void dfs(int nod)
{
    viz[nod]=1;
    st[++dr]=nod;
    for(iter it=g[nod].begin();it!=g[nod].end();it++)
    {
        if(!viz[*it])
            dfs(*it);
    }
}

void df(int nod)
{
    viz[nod]=1;
    s[k].push_back(nod);
    for(iter it=v[nod].begin();it!=v[nod].end();it++)
    {
        if(!viz[*it])
            df(*it);
    }
}

int main()
{
    fin>>n>>m;
    while(m--)
    {
        int x,y;
        fin>>x>>y;
        g[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    memset(viz,0,sizeof(viz));
    for(int i=dr;i>=1;i--)
        if(!viz[st[i]])
        {
            k++;
            df(st[i]);
        }
    fout<<k<<"\n";
    for(int i=1;i<=k;i++)
    {
        for(iter it=s[i].begin();it!=s[i].end();it++)
            fout<<*it<<" ";
        fout<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}