Cod sursa(job #1324928)

Utilizator span7aRazvan span7a Data 22 ianuarie 2015 22:23:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstdlib>
#include<iomanip>
#define maxN 100001
#define maxM 200001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int>G[maxN],Gt[maxN],sol[maxN];
stack<int>st;
int st_sol[maxN];
int n,m,t,nrc;
bool viz[maxN];
void df(int nod)
{
    viz[nod]=true;
    for(int i=0;i<G[nod].size();i++)
        if( viz[G[nod][i]] ==false )
              df(G[nod][i]);

    st_sol[++t]=nod;

}
void df2(int nod,int comp)
{
     viz[nod]=true;
     sol[comp].push_back(nod);
        for(int i=0;i<Gt[nod].size();i++)
            if( viz[Gt[nod][i]]==false )
            {
                df2(Gt[nod][i],comp);
            }
    }

void com_tari_conexe()
{
    int i,nod;
    for(i=n;i>=1;i--)
        if(viz[i] == false)
            df(i);
    fill(viz+1,viz+n+1,false);
    for(i=n;i>=1;i--)
    {
        nod=st_sol[i];

        if(!viz[nod])
        {
            nrc++;
            df2(nod,nrc);

        }
    }
}
void citire()
{
    int i,a,b;
     f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        G[a].push_back(b);
        Gt[b].push_back(a);
    }
}
void afisare()
{
    int i,j;
    g<<nrc<<'\n';
    for(i=1;i<=nrc;i++)
    {
        for(j=0;j<sol[i].size();j++)
            g<<sol[i][j]<<" ";

        g<<'\n';
    }

}
int main()
{
    citire();
    com_tari_conexe();
    afisare();
    return 0;
}