Cod sursa(job #1347960)

Utilizator roxana_97Soare Roxana Florentina roxana_97 Data 19 februarie 2015 13:23:57
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100099
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

int N, M, viz[NMAX], Tsort[NMAX], sol,x, y;
vector < int > G[NMAX], T[NMAX], CTC[NMAX];


void DFS(int node)
{
    viz[node]=1;
    for (vector<int>::iterator it=G[node].begin(); it!=G[node].end(); it++)
        if(!viz[*it]) DFS(*it);
    Tsort[++Tsort[0]]=node;
}

void DFS_T(int node)
{
    viz[node]=0; CTC[sol].push_back(node);
    for (vector<int>::iterator it=T[node].begin(); it!=T[node].end(); it++)
        if(viz[*it]) DFS_T(*it);
}

void GetCTC()
{
    for (int i=1; i <=N; i++)
        if(!viz[i]) DFS(i);
    for(int i=N; i>=1; --i)
        if(!viz[Tsort[i]])
            ++sol, DFS_T(Tsort[i]);
}

int main()
{
    f>>N>>M;
    for(int i=1; i<=M;i++)
        f>>x>>y, G[x].push_back(y), T[y].push_back(x);
    GetCTC();
    g<<sol<<'\n';
    for (int i=1; i<=sol; i++)
    {
        for (vector<int>::iterator it=CTC[i].begin(); it!=CTC[i].end(); it++)
                g<<*it<<' ';
        g<<'\n';
    }
    f.close();g.close();
    return 0;
}