Cod sursa(job #2168230)

Utilizator stefanst77Luca Stefan Ioan stefanst77 Data 14 martie 2018 10:06:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <vector>
#define Nmax 100005
#define inFile "ctc.in"
#define outFile "ctc.out"

using namespace std;

int N,st[Nmax],top,nrsol;
vector <int> L[Nmax], T[Nmax], sol[Nmax];
bool viz[Nmax];

inline void Read()
{
    int i,x,y,M;
    ifstream fin(inFile);
    fin >> N >> M;
    for(i = 1; i <= M; ++i)
    {
        fin>>x>>y;
        L[x].push_back(y);
        T[y].push_back(x);
    }
    fin.close();
}

inline void Dfs(int nod)
{
    int i, len, j;
    len = L[nod].size();
    viz[nod] = true;
    for(i = 0; i < len; ++i)
    {
        j = L[nod][i];
        if(!viz[j])
            Dfs(j);
    }
    st[++top]=nod;
}

inline void Dfs2(int nod)
{
    int i, len, j;
    len = T[nod].size();
    viz[nod] = true;
    for(i = 0; i < len; ++i)
    {
        j = T[nod][i];
        if(!viz[j])
            Dfs2(j);
    }
    sol[nrsol].push_back(nod);
}

inline void Solve()
{
    int i, nod;
    for(i = 1; i <= N; ++i)
        if(!viz[i])
            Dfs(i);
    for(i = 1; i <= N; ++i)
        viz[i] = false;
    while(top > 0)
    {
        nod = st[top--];
        if(!viz[nod])
        {
            ++nrsol;
            Dfs2(nod);
        }
    }
    ofstream fout(outFile);
    fout << nrsol << "\n";

    for(i = 1; i <= nrsol; ++i)
    {
        int len = sol[i].size();
        for(int j = 0; j < len; j++)
            fout << sol[i][j] << " ";
        fout << "\n";
    }
    fout.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}