Cod sursa(job #2285305)

Utilizator savulescustefanSavulescu Stefan savulescustefan Data 18 noiembrie 2018 14:07:33
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <vector>
using namespace std;
vector <int> b[100004],v[100004];
int n,m,x,y,nr,r,i,j,k,a[100004];
bool sel[100004];
void g (int x)
{
    int i,k;
    sel[x]=true;
    k=v[x].size()-1;
    for (i=0;i<=k;i++)
    {
        if (sel[v[x][i]]==false)
            g(v[x][i]);
    }
    a[++nr]=x;
}
void c (int x)
{
    int i,k;
    sel[x]=true;
    b[r].push_back(x);
    k=v[x].size()-1;
    for (i=0;i<=k;i++)
    {
        if (sel[v[x][i]]==false)
            c(v[x][i]);
    }
    return;
}
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);
        v[x].push_back(y);
    }
    for (i=1;i<=n;i++)
        sel[i]=false;
    nr=0;
    for (i=1;i<=n;i++)
    {
        if (sel[i]==false)
            g(i);
    }
    for (i=1;i<=n;i++)
        sel[i]=false;
    r=0;
    for (i=1;i<=n;i++)
    {
        if (sel[a[i]]==false)
        {
            r++;
            c(a[i]);
        }
    }
    printf ("%d\n", r);
    for (i=1;i<=r;i++)
    {
        k=b[i].size()-1;
        for (j=0;j<=k;j++)
            printf ("%d ", b[i][j]);
        printf ("\n");
    }
    return 0;
}