Cod sursa(job #941069)

Utilizator VisuianMihaiMihai Visuian VisuianMihai Data 17 aprilie 2013 20:57:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, x, y, nrCtc;
vector<int>g[100001], gt[100001], c[100001];
vector<int>discovered;
bool vis[100001];
void Dfs(int x)
{
    if(vis[x]) return;
    vis[x]=true;
    for(vector<int>::iterator it=g[x].begin(); it<g[x].end(); it++ )
        Dfs(*it);
    discovered.push_back(x);
}
void Dfs2(int x)
{
    if(vis[x]) return;
    vis[x]=true;
    for(vector<int>::iterator it=gt[x].begin(); it<gt[x].end(); it++ )
        Dfs2(*it);
    c[nrCtc].push_back(x);
}
int main()
{
    fin>>n>>m;
    for(int i = 1; i<= m; i++ )
    {
        fin>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    for(int i = 1; i<= n; i++ )
        Dfs(i);
    memset(vis,0,sizeof(vis));
    for(;discovered.size();discovered.pop_back())
        if( !vis[discovered.back()] )
        {
            nrCtc++;
            Dfs2(discovered.back());
        }
    fout<<nrCtc << '\n';
    for(int i = 1; i<= nrCtc; i++ )
    {
        sort(c[i].begin(),c[i].end());
        for(vector<int>::iterator it=c[i].begin(); it<c[i].end(); it++)
            fout<<*it<<' ';
        fout<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}