Cod sursa(job #3229808)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 17 mai 2024 16:43:57
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int> v[100001],vt[100001],sol;
vector <vector <int>> solf;
int s[100001],n,m,x,y,i,k,j;
bitset <100001> viz;
void dfs_sort_top (int nod)
{
    viz[nod]=1;
    for (int i=0; i<v[nod].size (); i++)
    {
        int vecin=v[nod][i];
        if (!viz[vecin])
            dfs_sort_top (vecin);
    }
    s[++k]=nod;
}
void dfs (int nod)
{
    viz[nod]=1;
    sol.push_back (nod);
    for (int i=0; i<vt[nod].size (); i++)
    {
        int vecin=vt[nod][i];
        if (!viz[vecin])
            dfs (vecin);
    }
}
int main ()
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        fin>>x>>y;
        v[x].push_back (y);
        vt[y].push_back (x);
    }
    for (i=1; i<=n; i++)
    {
        if (!viz[i])
            dfs_sort_top (i);
    }
    viz.reset ();
    reverse (s+1,s+n+1);
    for (i=1; i<=n; i++)
    {
        sol.clear ();
        if (!viz[s[i]])
        {
            dfs (s[i]);
            solf.push_back (sol);
        }
    }
    fout<<solf.size ()<<"\n";
    for (i=0; i<solf.size (); i++)
    {
        for (j=0; j<solf[i].size (); j++)
            fout<<solf[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}