Pagini recente » Cod sursa (job #1333022) | Cod sursa (job #1870774) | Cod sursa (job #1166584) | Cod sursa (job #219642) | Cod sursa (job #2927821)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m;
// Facem o clasa nod pentru a retine informatiile despre noduri
// Aici retinem lista de vecini pentru fiecare nod si lista de vecini daca muchiile ar fi inversate
class node
{
public:
vector <int> adicente;
vector <int> rev_adiacente;
};
// Lista de noduri
vector <node> noduri;
int numar_componente = 0;
// Vector de vizitati
int vizitat[100000];
// Facem un stack pentru a retine nodurile in care ajungem si am terminat de vizitat toti vecinii
stack <int> s;
vector <vector <int>> componente;
void dfs1(int start)
{
// Marcam nodul ca vizitat
vizitat[start] = 1;
// Parcurgem lista de vecini
for (int i = 0; i < noduri[start].adicente.size(); i++)
{
// Daca nu a fost vizitat, il vizitam
if (vizitat[noduri[start].adicente[i]] == 0)
{
dfs1(noduri[start].adicente[i]);
}
}
// Adaugam nodul in stack dupa ce am terminat de vizitat toti vecinii lui
s.push(start);
}
void dfs2(int start)
{
// Adaugam in componenta tare conexa
componente[numar_componente].push_back(start);
// Marcam nodul ca vizitat
vizitat[start] = 1;
// Parcurgem lista de vecini
for (int i = 0; i < noduri[start].rev_adiacente.size(); i++)
{
// Daca nu a fost vizitat, il vizitam
if (vizitat[noduri[start].rev_adiacente[i]] == 0)
{
dfs2(noduri[start].rev_adiacente[i]);
}
}
}
void kosaraju()
{
// Facem dfs pentru
for(int i = 0; i < n; i++)
if(!vizitat[i])
dfs1(i);
// Resetam vectorul de vizitati
for(int i = 0; i < n; i++)
vizitat[i] = 0;
// Parcurgem stack-ul si facem dfs pentru fiecare nod din stack
// cu muchiile inversate
while (!s.empty())
{
int nod = s.top();
s.pop();
// Daca nu e vizitat inseamna ca e o componenta tare conexa noua
if (!vizitat[nod])
{
dfs2(nod);
numar_componente++;
}
}
}
int main()
{
fin >> n >> m;
noduri.resize(n + 1);
componente.resize(n + 1);
for(int i = 0; i < m; i++)
{
int x, y;
fin >> x >> y;
// Adaugam muchia in lista de vecini a nodului x si la lista inversata
noduri[x].adicente.push_back(y);
noduri[y].rev_adiacente.push_back(x);
}
// Aplicam algoritmul lui Kosaraju
kosaraju();
fout << numar_componente << '\n';
for(int i = 0; i < numar_componente; i++)
{
for (int j = 0; j < componente[i].size(); j++)
fout << componente[i][j] << " ";
fout << '\n';
}
return 0;
}