Pagini recente » Cod sursa (job #3151361) | Cod sursa (job #2446365) | Cod sursa (job #3273393) | Cod sursa (job #2769312) | Cod sursa (job #2668555)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int const NMAX = 100001;
int n, m, nr_comp_tare_conexe, viz[NMAX];
vector<int> arce[100001], arceTranspusa[NMAX];
stack<int> stiva; ///folosim o stiva pentru a retine parcurgerea grafului si pt a adauga recursiv elementele in aceasta
vector<int> componenteTareConexe[NMAX]; ///vector pentru componentele tare conexe
void citire()
{
f >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
f >> x >> y;
arce[x].push_back(y); ///inseram in lista de arce
arceTranspusa[y].push_back(x); ///inseram arcul cu directie opusa in lista de arce transpuse
}
}
void DFS(int nod)
{
viz[nod] = 1;
for(int i = 0; i < arce[nod].size(); i++)
{
int vecin = arce[nod][i];
if(viz[vecin] == 0)
DFS(vecin);
}
stiva.push(nod); ///salvam pe stiva ordinea nodurilor
}
void DFS_transpus(int nod)
{
viz[nod] = 2; ///marcam cu 2 a doua parcurgere a unui nod din graful transpus
componenteTareConexe[nr_comp_tare_conexe].push_back(nod); ///adaugam nodul in lista de componente tare conexe
for(int i = 0; i < arceTranspusa[nod].size(); i++)
{
int vecin = arceTranspusa[nod][i];
if(viz[vecin] == 1) ///verificam daca vecinul a fost vizitat in prima parcurgere dfs
DFS_transpus(vecin);
}
}
void afis()
{
g << nr_comp_tare_conexe << '\n';
for(int i = 1; i <= nr_comp_tare_conexe; i++)
{
for(int j = 0; j < componenteTareConexe[i].size(); j++)
g << componenteTareConexe[i][j] << ' ';
g << '\n';
}
}
int main()
{
citire();
//
for(int i = 1; i <= n; i++)
if(viz[i] == 0)
DFS(i);
//
while(!stiva.empty())
{
int nod_curent = stiva.top(); ///luam nodul curent din varful stivei
if(viz[nod_curent] == 1)
{
nr_comp_tare_conexe++;
DFS_transpus(nod_curent);
}
stiva.pop();
}
//
afis();
return 0;
}