Cod sursa(job #2140798)

Utilizator andreimuthMuth Andrei andreimuth Data 23 februarie 2018 21:29:39
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <cstring>
#include <vector>
#define nmax 100001
using namespace std;
 ifstream fin("ctc.in");
ofstream fout("ctc.out");

int viz[nmax], st[nmax];
int sol, n, m, i, j, x, y;

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

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

inline void dfst (int nod)
{
    int i;
    viz[nod] = 1;
    for (i=0; i < gt[nod].size(); i++)
    {
        if(!viz[gt[nod][i]])
            dfst (gt[nod][i]);
    }
    ctc[sol].push_back (nod);
}
int main()
{
    fin>>n>>m;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    memset(st, 0, sizeof (st));
    memset(viz, 0, sizeof (viz));

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

    memset(viz, 0, sizeof(viz));

    for (i = n; i > 0; i--)
    {
        if(!viz[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;
}