Cod sursa(job #3246168)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 2 octombrie 2024 08:56:58
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int> s,v[100001],vt[100001];
vector <vector <int>> sol;
bitset <100001> viz;
int n,m,x,y,i,j,k,stiva[100001];
void dfs_stiva (int nod)
{
    viz[nod]=1;
    for (int i=0; i<v[nod].size (); i++)
    {
        int vecin=v[nod][i];
        if (!viz[vecin])
            dfs_stiva (vecin);
    }
    stiva[++k]=nod;
}
void dfs_ctc (int nod)
{
    viz[nod]=1;
    s.push_back (nod);
    for (int i=0; i<vt[nod].size (); i++)
    {
        int vecin=vt[nod][i];
        if (!viz[vecin])
            dfs_ctc (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_stiva (i);
    }
    viz.reset ();
    for (i=1; i<=n; i++)
    {
        if (!viz[i])
        {
            s.clear ();
            dfs_ctc (i);
            sol.push_back (s);
        }
    }
    fout<<sol.size ()<<"\n";
    for (i=0; i<sol.size (); i++)
    {
        for (j=0; j<sol[i].size (); j++)
            fout<<sol[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}