Cod sursa(job #2169969)

Utilizator MaaaaaCristina Ma Maaaaa Data 14 martie 2018 19:57:14
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 100005
#define mmax 200005
using namespace std;
fstream f1("ctc.in", ios::in);
fstream f2("ctc.out", ios::out);
int n, m, nrcomp, viz[nmax], l[nmax], nrl;
vector <int> v[nmax], vt[nmax], comp[nmax];
///pui nodurile in lsta l de la stanga la dreapta (dfs, pui nodul care nu mai are vecini nezivitati)
///parcurgi lista de la dreapta la stanga si din fiecare nod, nodurile in care ajungi fac parte din aceeasi componenta conexa cu acesta
void citire()
{
    int i, x, y;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y;
        v[x].push_back(y);
        vt[y].push_back(x);
    }
}
void dfs(int nod)
{
    viz[nod]=1;
    for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
        if(!viz[*it])
           dfs(*it);
    nrl++; l[nrl]=nod;
}
void dfs_t(int nod)
{
    viz[nod]=1;
    for(auto it=vt[nod].begin(); it!=vt[nod].end(); ++it)
        if(!viz[*it])
            {
                dfs_t(*it);
                comp[nrcomp].push_back(*it);
            }
}
void solve()
{
    int i;
    for(i=1; i<=n; i++) viz[i]=0;
    for(i=nrl; i>=1; i--)
        if(!viz[l[i]])
        {
            nrcomp++;
            comp[nrcomp].push_back(l[i]);
            dfs_t(l[i]);
        }
}
void afis()
{
    int i;
    f2<<nrcomp<<"\n";
    for(i=1; i<=nrcomp; i++)
    {
        sort(comp[i].begin(), comp[i].end());
        for(auto it=comp[i].begin(); it!=comp[i].end(); ++it)
            f2<<*it<<' ';
        f2<<"\n";
    }
}
int main()
{
    citire();
    for(int i=1; i<=n; i++)
       if(!viz[i]) dfs(i);
    solve();
    afis();
    return 0;
}