Cod sursa(job #1023014)

Utilizator a96tudorAvram Tudor a96tudor Data 6 noiembrie 2013 12:04:42
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
// componente tare conexe
#include<cstdio>
#include<vector>
#include<cstring>


#define N_MAX 100010
#define M_MAX 200010
#define pb push_back
using namespace std;

vector <int> G[N_MAX];
vector <int> Gt[N_MAX];

bool sel[N_MAX];
int  St[N_MAX];

int N,i,NR_SOL,p;

//DF pe graful transpus

inline void DF_Trans(int x,bool ok)
{
    vector <int> :: iterator it;
    if (ok) printf("%d ",x);
    sel[x]=true;
    for (it=Gt[x].begin();it!=Gt[x].end();++it)
        if (!sel[*it]) DF_Trans(*it, ok);

}


// DF pe graful original

inline void DF(int x)
{
    vector <int> :: iterator it;
    sel[x]=true;
    for (it=G[x].begin();it!=G[x].end();++it)
        if (!sel[*it]) DF(*it);
    St[++p]=x;
}

inline void Read_Data()
{
    int M,i,x,y;
    scanf("%d%d",&N,&M);
    for (i=1;i<=M;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].pb(y);
        Gt[y].pb(x);
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    Read_Data();
    for (i=1;i<=N;i++)
        sel[i]=false;
    p=0;
    for (i=1;i<=N;i++)
        if (!sel[i]) DF(i);


    // determinarea numarului de componente

    NR_SOL=0;
    for (i=1;i<=N;i++)
        sel[i]=false;
    for (i=N;i>0;--i)
        if (!sel[St[i]])
            {
                DF_Trans(St[i],false);
                NR_SOL++;
            }

    printf("%d\n",NR_SOL);

    //afisarea componentelor

    for (i=1;i<=N;i++)
        sel[i]=false;
    for (i=N;i>0;--i)
        if (!sel[St[i]])
            {
                DF_Trans(St[i],true);
                printf("\n");
            }
    fclose(stdin);
    fclose(stdout);
    return 0;
}