Cod sursa(job #1836227)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 27 decembrie 2016 23:32:03
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
#define VAL 100005

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int N, M, a, b, i, j;
int sir[VAL], x[VAL];
int poz[VAL], K;
vector<int> v[VAL];
vector<int> G[VAL];
vector<int> comp[VAL];
vector<int> :: iterator it;

void dfs(int nr)
{
    vector<int> :: iterator it;
    x[nr]=K;
    comp[K].push_back(nr);
    for (it=G[nr].begin(); it!=G[nr].end(); it++)
      if (x[*it]<1 && poz[*it]>=poz[sir[i]])
        dfs(*it);
}

int main()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> a >> b;
        v[a].push_back(b);
        G[b].push_back(a);
        x[b]++;
    }
    for (i=1; i<=N; i++)
    {
        if (x[i]==0)
        {
            sir[++K]=i;
            poz[i]=K;
        }
    }
    for (i=1; i<=N; i++)
    {
        for (it=v[i].begin(); it!=v[i].end(); it++)
        {
            x[*it]--;
            if (x[*it]==0)
            {
                sir[++K]=*it;
                poz[*it]=K;
            }
        }
    }
    K=0;
    for (i=1; i<=N; i++)
    {
        if (x[sir[i]]<1)
        {
            ++K;
            dfs(sir[i]);
        }
    }
    fout << K << '\n';
    for (i=1; i<=K; i++)
    {
        for (it=comp[i].begin(); it!=comp[i].end(); it++)
          fout << *it << " ";
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}