Cod sursa(job #1142851)

Utilizator j.loves_rockJessica Joanne Patrascu j.loves_rock Data 14 martie 2014 12:13:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
# include <cstdio>
# include <cstring>
# include <vector>
# define N 100010
# define M 200010
# define bg begin()
# define ed end()
# define pb push_back

using namespace std;

vector <int> G[N],GT[N];
int n,m,i,nc;
bool sel[N];
int ST[N];
bool ok;

void load()
{
    int i,x,y;
    scanf("%d %d\n", &n, &m);
    for(i=1; i<=m; ++i)
    {
        scanf("%d %d\n", &x, &y);
        G[x].pb(y);
        GT[y].pb(x);
    }
}
void Df1(int nod)
{
    vector <int> :: iterator it;
    sel[nod]=true;
    for(it=G[nod].bg; it!=G[nod].ed; ++it)
        if(!sel[(*it)])
            Df1((*it));
    ST[++ST[0]]=nod;
}
void Df2(int nod, bool ok)
{
    vector <int> :: iterator it;
    sel[nod]=true;
    if(ok) printf("%d ", nod);
    for(it=GT[nod].bg; it!=GT[nod].ed; ++it)
        if(!sel[(*it)])
            Df2((*it),ok);
}
int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    load();
    for(i=1; i<=n; ++i)
        if(!sel[i])
            Df1(i);
    memset(sel,false,sizeof(sel));
    for(i=ST[0]; i>0; --i)
        if(!sel[ST[i]])
        {
            ok=false;
            Df2(ST[i],ok);
            nc++;
        }
    printf("%d\n", nc);
    memset(sel,false,sizeof(sel));
    for(i=ST[0]; i>0; --i)
        if(!sel[ST[i]])
        {
            ok=true;
            Df2(ST[i],ok);
            printf("\n");
        }
    return 0;
}