Cod sursa(job #1263206)

Utilizator sorynsooSorin Soo sorynsoo Data 14 noiembrie 2014 08:43:12
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 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,st;
int d[100005],ordine[100005];
bool fol[100005],fol_cr[100005],ok;
vector<int> graf[100005],graft[100005],rasp[100005];
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)
{
    int i,x;
    if(nod==st && fol[nod])
        ok=true;
    for(i=0; i<graft[nod].size(); i++)
    {
        x=graft[nod][i];
        if(!fol[graft[nod][i]] && !fol_cr[graft[nod][i]])
        {
            fol[graft[nod][i]]=1;
            fol_cr[graft[nod][i]]=1;
            bfs_t(graft[nod][i]);
            if(ok==false)
                fol[graft[nod][i]]=0;
            else
                rasp[nr_comp].push_back(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[ordine[i]])
        {
            for(j=1; j<=n; j++)
                fol_cr[j]=0;
            ++nr_comp;
            st=ordine[i]; ok=false;
            bfs_t(ordine[i]);
            if(!ok)
            {
                rasp[nr_comp].push_back(ordine[i]);
                fol[ordine[i]]=1;
            }
        }
    }
    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";
    }


}