Cod sursa(job #2287816)

Utilizator alex.carpCarp Alexandru alex.carp Data 22 noiembrie 2018 15:43:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g1("ctc.out");
const int NMAX=100010;
vector<int>g[NMAX],gt[NMAX],v[NMAX];
stack<int>noduri;
int n,m,ctc;
bool vizitat[NMAX];
void citire()
{
    int x,y;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
}
void dfs(int i)
{
    vizitat[i]=1;
    for(int t=0;t<g[i].size();t++)
    {
        if(vizitat[g[i][t]]==0)
            dfs(g[i][t]);
    }
    noduri.push(i);
}
void dfsgt(int i)
{
    vizitat[i]=1;
    v[ctc].push_back(i);
    for(int t=0;t<gt[i].size();t++)
    {
        if(vizitat[gt[i][t]]==0)
            dfsgt(gt[i][t]);
    }
}
void afisare()
{
    g1<<ctc<<'\n';
    for(int i=1;i<=ctc;i++)
    {
        for(int j=0;j<v[i].size();j++)
            g1<<v[i][j]<<" ";
        g1<<'\n';
    }
}
int main()
{citire();
for(int i=1;i<=n;i++)
    if(vizitat[i]==0)dfs(i);
for(int i=1;i<=n;i++)
    vizitat[i]=0;
while(!noduri.empty())
{
    int ncrt=noduri.top();
    noduri.pop();
    if(vizitat[ncrt]==0)
    {
        ctc++;
        dfsgt(ncrt);
    }
}
afisare();

    return 0;
}