Cod sursa(job #1788815)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 26 octombrie 2016 15:25:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <cstdio>
#include <vector>

using namespace std;

struct Nod
{
    vector<int> v;
    vector<int> t;
    int s, viz;
} v[100000];
vector<int> r[100000];
int lr = 0, a[100000], la = 0;

void parc(int n)
{
    if(v[n].s == 1 || v[n].viz == 1)
        return;
    a[la++] = n;
    v[n].s = 1;
    v[n].viz = 1;
    for(int i = 0; i < v[n].v.size(); i++)
        parc(v[n].v[i]);
}

void parct(int n)
{
    if(v[n].s == 0)
        return;
    v[n].s = 0;
    r[lr].push_back(n);
    for(int i = 0; i < v[n].t.size(); i++)
        parct(v[n].t[i]);
}

int main()
{
    int x, y, n, m, i, j;
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    scanf("%d %d\n", &n, &m);
    for(i = 0; i < n; i++)
    {
        v[i].s = 0;
        v[i].viz = 0;
    }
    for(i = 0; i < m; i++)
    {
        scanf("%d %d\n", &x, &y);
        x--; y--;
        v[x].v.push_back(y);
        v[y].t.push_back(x);
    }
    for(i = 0; i < n; i++)
    {
        if(v[i].viz != 0)
            continue;
        la = 0;
        parc(i);
        for(j = 0; j < la; j++)
        {
            if(v[a[j]].s == 1)
            {
                parct(a[j]);
                lr++;
            }
        }
    }
    printf("%d\n", lr);
    for(i = 0; i < lr; i++)
    {
        for(j = 0; j < r[i].size(); j++)
        {
            printf("%d ", r[i][j] + 1);
        }
        printf("\n");
    }
    return 0;
}