Cod sursa(job #2330088)

Utilizator XDDDDariusPetean Darius XDDDDarius Data 27 ianuarie 2019 20:40:33
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <stack>
#include <set>
#include <vector>
#define NMAX 100005
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");

using namespace std;
stack < int > s;
vector < int > graf[NMAX],trans[NMAX];
set < int > conex[NMAX];
int nr_sol;
bool viz[NMAX];

void dfs(int nod)
{
    viz[nod]=1;
    for(auto vecini : graf[nod])
    {
        if(!viz[vecini])
        {
            dfs(vecini);
        }
    }
    s.push(nod);
}

void dfs_transpus(int nod)
{
    viz[nod]=1;
    for(auto vecini : trans[nod])
    {
        if(!viz[vecini])
        {
            conex[nr_sol].insert(vecini);
            dfs_transpus(vecini);
        }
    }
}
int n,m;
int x,y;
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y;
        graf[x].push_back(y);
        trans[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!viz[i])
            dfs(i);
    }
    memset(viz,0,sizeof(viz));
    while(!s.empty())
    {
        if(!viz[s.top()])
        {
            conex[nr_sol].insert(s.top());
            dfs_transpus(s.top());
            nr_sol++;
        }
        s.pop();
    }
    out<<nr_sol<<'\n';
    for(int i=0;i<nr_sol;i++)
    {
        for(auto e : conex[i])
        {
            out<<e<<" ";
        }
        out<<"\n";
    }
    return 0;
}