Cod sursa(job #1261916)

Utilizator sorynsooSorin Soo sorynsoo Data 12 noiembrie 2014 20:30:55
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n,m,i,j,x,y,nod,nr,nr_comp;
int d[100001],ordine[100001];
bool fol[100001];
vector<int> graf[100001],graft[100001],rasp[100001];
void bfs(int nod)
{
    for(int i=0; i<graf[nod].size(); i++)
    {
        if(!fol[graf[nod][i]])
        {
            fol[graf[nod][i]]=1;
            d[graf[nod][i]]=nr-1; nr--;
            bfs(graf[nod][i]);
        }
    }
}
void bfs_t(int nod)
{
    for(int i=0; i<graft[nod].size(); i++)
    {
        if(!fol[graft[nod][i]])
        {
            fol[graft[nod][i]]=1;
            rasp[nr_comp].push_back(graft[nod][i]);
            bfs_t(graft[nod][i]);
        }
    }
}
int main()
{
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y;
        graf[x].push_back(y); // graful normal
        graft[y].push_back(x); // graful transpus
    }
    d[1]=n; fol[1]=1; nr=n;
    bfs(1); // fac bfs si atrbui in d[i] timpul la care a fost prelucrat nodu i ( ordine descrescatoare )
    for(i=1; i<=n; i++) // sortez nodurile in ordine descrescatoare
        ordine[n-d[i]+1]=i;

    nr_comp=0;
    for(i=1; i<=n; i++)
        fol[i]=0;
    for(i=1; i<=n; i++)
    {
        if(!fol[i])
        {
            fol[i]=1;
            rasp[++nr_comp].push_back(i);
            bfs_t(i);
        }
    }
    cout<<nr_comp<<"\n";
    for(i=1; i<=nr_comp; i++)
    {
        for(j=0; j<rasp[i].size(); j++)
            cout<<rasp[i][j]<<" ";
        cout<<"\n";
    }

}