Cod sursa(job #1834347)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 24 decembrie 2016 13:58:57
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <cstdio>
#include <vector>
#define VAL 100005

using namespace std;

int N, M, i, j;
int x, y, K;
int gasit[VAL];
int ok[VAL], ok2[VAL];
vector<int> G[VAL];
vector<int> Ginv[VAL];
vector<int> comp[VAL];
vector<int> :: iterator it;

void dfs(int x, vector<int> Graf[], int gas[], int pas)
{
    vector<int> :: iterator it;
    gas[x]=K;
    if (pas==2 && ok[x]==K)
      gasit[x]=K;
    for (it=Graf[x].begin(); it!=Graf[x].end(); it++)
      if (gas[*it]<K)
        dfs(*it, Graf, gas, pas);
}

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].push_back(y);
        Ginv[y].push_back(x);
    }
    for (i=1; i<=N; i++)
    {
        if (gasit[i]==0)
        {
            ++K;
            gasit[i]=K;
            comp[K].push_back(i);
            ok[i]=K;
            dfs(i, G, ok, 1);
            ok2[i]=K;
            dfs(i, Ginv, ok2, 2);
        }
        else
          comp[gasit[i]].push_back(i);
    }
    printf("%d\n", K);
    for (i=1; i<=K; i++)
    {
        for (it=comp[i].begin(); it!=comp[i].end(); it++)
          printf("%d ", *it);
        printf("\n");
    }
    return 0;
}