Cod sursa(job #1836245)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 28 decembrie 2016 00:38:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 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 st[VAL], top;
int loc[VAL], K;
bool viz[VAL];
vector<int> v[VAL];
vector<int> G[VAL];
vector<int> comp[VAL];
vector<int> :: iterator it;

void visit(int i)
{
    vector<int> :: iterator it;
    if (viz[i]==false)
    {
        viz[i]=true;
        for (it=v[i].begin(); it!=v[i].end(); it++)
          visit(*it);
        st[++top]=i;
    }
}

void ataseaza(int i, int root)
{
    vector<int> :: iterator it;
    if (loc[i]==0)
    {
        loc[i]=root;
        comp[root].push_back(i);
        for (it=G[i].begin(); it!=G[i].end(); it++)
          ataseaza(*it, root);
    }
}

int main()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> a >> b;
        v[a].push_back(b);
        G[b].push_back(a);
    }
    for (i=1; i<=N; i++)
      visit(i);
    while (top!=0)
    {
        ataseaza(st[top], st[top]);
        top--;
    }
    for (i=1; i<=N; i++)
      if (comp[i].size()!=0)
        K++;
    fout << K << '\n';
    for (i=1; i<=N; i++)
    {
        if (comp[i].size()>0)
        {
            for (it=comp[i].begin(); it!=comp[i].end(); it++)
              fout << *it << " ";
            fout << '\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}