Cod sursa(job #1022080)

Utilizator bodyionitaIonita Bogdan Constantin bodyionita Data 4 noiembrie 2013 18:47:16
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define pb push_back
using namespace std;

int i, x, y, N, M, NR;
vector<int> G[100001], GT[100001], Sol[100001], Stiva;
bool Sel[100001];

inline void DF(int);
inline void DFT(int);
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d", &N, &M);
    for (i=1; i<=M; i++)
    {
        scanf("%d%d", &x, &y);
        G[x].pb(y);
        GT[y].pb(x);
    }
    ////////////////////////////////////////
    DF(1);
    ////////////////////////////////////////
    memset(Sel, false, sizeof(Sel));
    for (i=Stiva.size()-1; i>=0; i--)
        if (!Sel[Stiva[i]])
        {
            NR++;
            DFT(Stiva[i]);
        }
    /////////////////////////////////////////
    printf("%d\n", NR);
    for (i=1; i<=NR; i++)
    {
        for (vector<int>::iterator it=Sol[i].begin(); it!=Sol[i].end(); it++)
            printf("%d ",*it);
        printf("\n");
    }
    return 0;
}

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

inline void DFT(int x)
{
    Sel[x]=true;
    Sol[NR].pb(x);
    for (vector<int>::iterator it=GT[x].begin(); it!=GT[x].end(); it++)
        if (!Sel[*it]) DFT(*it);
}