Cod sursa(job #2140718)

Utilizator calinlixandruLixandru Calin-Mihai calinlixandru Data 23 februarie 2018 20:02:48
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <cstring>

#define Nmax 100001

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;
}