Cod sursa(job #1612641)

Utilizator elevenstrArina Raileanu elevenstr Data 24 februarie 2016 23:00:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>

using namespace std;
FILE* fila=fopen("ctc.in","r");
ofstream out("ctc.out");
#define MAX 100009
vector <int> v[MAX],rev[MAX],Sol[MAX];
int n,m,viz[MAX],k;
stack <int> S;
void kosaraju(int nod)
{
    viz[nod]=1;
    int t=1;
    for(int i=0; i<v[nod].size(); i++)
        if(!viz[v[nod][i]])kosaraju(v[nod][i]);
    S.push(nod);
}
void rev_kos(int nod)
{
    Sol[k].push_back(nod);
    viz[nod]=1;
    for(int i=0; i<rev[nod].size(); i++)
        if(!viz[rev[nod][i]])rev_kos(rev[nod][i]);
}
#define LIM 5000
char buff[5001];
int poz;
void cit (int &nr)
{
    while(!isdigit(buff[poz]))
    {
        ++poz;
        if(poz==LIM){poz=0;fread(buff,1,LIM,fila);}
    }
    nr=0;
    while(isdigit(buff[poz]))
    {
        nr=nr*10+buff[poz]-'0';
        ++poz;
         if(poz==LIM){poz=0;fread(buff,1,LIM,fila);}
    }
}
int main()
{
    cit(n);cit(m);
    while(m--)
    {
        int a,b;
        cit(a);cit(b);
        v[a].push_back(b);
        rev[b].push_back(a);
    }
    for(int i=1; i<=n; i++)
        if(!viz[i])kosaraju(i);

    for(int i=1; i<=n; i++)
      viz[i]=0;
    while(!S.empty())
    {
        int x=S.top();
        if(!viz[x])
        {
            ++k;
            rev_kos(x);
        }
        S.pop();
    }
    out<<k<<'\n';
    for(int i=1; i<=k; i++)
    {
        while(!Sol[i].empty())
        {
            out<<Sol[i].back()<<" ";
            Sol[i].pop_back();
        }
        out<<'\n';
    }
    return 0;
}