Cod sursa(job #2140678)

Utilizator IonelChisIonel Chis IonelChis Data 23 februarie 2018 19:23:22
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <cstring>

#define Nmax 100002

using namespace std;

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

int fv[Nmax], st[Nmax], sol, n, m, i, j;

vector <int> g[Nmax], gt[Nmax], ctc[Nmax];
vector <int> :: iterator it;

inline void dfs(int nod)
{
    int i;
    fv[nod] = 1;
    for (i = 0; i < g[nod].size(); i ++)
    {
        if (!fv[g[nod][i]])
            dfs(g[nod][i]);
    }
    st[++st[0]] = nod;
}

inline void dfst(int nod)
{
    int i;
    fv[nod] = 1;
    for (i = 0; i < gt[nod].size(); i ++)
    {
        if (!fv[gt[nod][i]])
            dfst(gt[nod][i]);
    }
    ctc[sol].push_back(nod);
}


int main()
{
    fin >> n >> m;
    while (fin >> i >> j)
    {
        g[i].push_back(j);
        gt[j].push_back(i);
    }
    memset(st, 0, sizeof(st));
    memset(fv, 0, sizeof(fv));

    for (i = 1; i <= n; i ++)
    {
        if (!fv[i])
            dfs(i);
    }

    memset(fv, 0, sizeof(fv));

    for (i = n; i > 0; i --)
    {
        if (!fv[st[i]])
        {
            sol ++;
            dfst(st[i]);
        }
    }

    fout<<sol<<'\n';
    for (i = 1; i <= sol; i ++)
    {
        for (j = 0; j < ctc[i].size(); j ++)
            fout<<ctc[i][j]<<" ";
        fout<<'\n';
    }


    fin.close();
    fout.close();
    return 0;
}