Cod sursa(job #1380224)

Utilizator Denisa13Stefan Denisa Denisa13 Data 6 martie 2015 23:53:37
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector <int> G[100005], stiva, CTC[100005];
int t_intrare[100005], t_minim[100005];
bool viz[100005];

void dfs(int nod, int k, int &nr)
{
    int i;
    viz[nod]=1;
    t_intrare[nod]=t_minim[nod]=k;
    stiva.push_back(nod);
    for(i=0;i<G[nod].size();i++)
        {if(viz[G[nod][i]]==0)
            dfs(G[nod][i],k+1,nr);
        if(t_minim[G[nod][i]]<t_minim[nod])
                t_minim[nod]=t_minim[G[nod][i]];
        }
    if(t_minim[nod]==t_intrare[nod])
    {
        nr++;
        while(stiva.back()!=nod)
        {
            CTC[nr].push_back(stiva.back());
            stiva.pop_back();
        }
        CTC[nr].push_back(stiva.back());
            stiva.pop_back();
    }
}
int main()
{
    int n,m,i,x,y,nr=0,j;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        G[x].push_back(y);
    }
    for(i=1;i<=n;i++)
        if(viz[i]==0)
            dfs(i,1,nr);
    g<<nr<<'\n';
    for(i=1;i<=nr;i++)
    {
        for(j=0;j<CTC[i].size();j++)
            g<<CTC[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}