Cod sursa(job #941655)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 19 aprilie 2013 11:59:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;

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

vector<int> v[100001];
vector<int> rv[100001];
vector<int> ctc[100001];
bool used[100001];
stack<int> Q;
int n,m,nr;

void dfs(int nod)
{
    used[nod] = true;
    for(vector<int>::iterator it = v[nod].begin(); it!=v[nod].end();it++)
        if(!used[*it])
            dfs(*it);
    Q.push(nod);
}

void dfs2(int nod)
{
    used[nod] = true;
    for(vector<int>::iterator it = rv[nod].begin(); it!=rv[nod].end();it++)
        if(!used[*it])
            dfs2(*it);
    ctc[nr].push_back(nod);
}

int main()
{
    fin>>n>>m;
    for(int i = 1,x,y; i<= m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        rv[y].push_back(x);
    }

    for(int i=1;i<=n;i++)
        if(!used[i])
            dfs(i);
    memset(used,0,sizeof(used));

    while(!Q.empty())
    {
        int x = Q.top();
        if(!used[x])
            nr++,dfs2(x);
        Q.pop();
    }


    fout<<nr<<'\n';
    for(int i = 1; i<=nr;i++)
    {
        sort(ctc[i].begin(),ctc[i].end());
        for(vector<int>::iterator it = ctc[i].begin();it!= ctc[i].end();it++)
            fout<<*it<<' ';
        fout<<'\n';
    }

    fin.close();
    fout.close();
    return 0;
}