Pagini recente » Cod sursa (job #439471) | Cod sursa (job #2878194) | Cod sursa (job #645776) | Cod sursa (job #915231) | Cod sursa (job #2664565)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
//similar cu minimizarea dfa de la LFA
//Algoritmul lui Kosaraju
vector<int> adiacenta[100009];
vector<int> transpusa[100009];///se inverseaza sensul arcelor =>o parcurgere DFS determina o componenta conexa
vector<int> componente_conexe[100009];///pe pozitia 1 vom aveam lista cu nodurile primei componenete conexte ... pe pozitia nr_comp vom avea ultima componenta conexa
int vizitat [100009];///initializat cu zero
stack<int> stiva;
int nr_comp;
void DFS(int nod)
{
vizitat[nod] = 1;
for(size_t i=0; i<adiacenta[nod].size(); i++) {
if(!vizitat[adiacenta[nod][i]])
DFS(adiacenta[nod][i]);
}
///ca la sortarea topologica se salveaza nodul dupa ce ne-am intors din parcurgerea recursiva in stiva
stiva.push(nod);
}
void DFS2(int nod)
{
vizitat[nod] = 2;///il vizitam a doua oara in gradul transpus
componente_conexe[nr_comp].push_back(nod);///il inseram in componenta conexa din care face parte
for(size_t i=0; i<transpusa[nod].size();i++) {
if(vizitat[transpusa[nod][i]] == 1)
DFS2(transpusa[nod][i]);
}
}
int main()
{
int N,M,x,y;
in>>N>>M;
for(int i =1; i <=M ;i++)
{
in>>x>>y;
adiacenta[x].push_back(y);//graf orientat x y muchie => doar x e vecinul lui y
transpusa[y].push_back(x);//construim tanspusa grafului dat;
}
for(int i = 1; i <= N; i++)
{
if(!vizitat[i])
DFS(i);
}
//stiva.erase( unique( arr.begin(), arr.end() ), arr.end() );
while(!stiva.empty())//scoatem nodurile din stiva;
{
int nod = stiva.top();
if(vizitat[nod] == 1)///daca elem din stiva nu a fost vizitat si in parcurgerea transpusei
{
nr_comp ++;///inseamna ca apartine unei alte componente conexe
DFS2(nod);
}
stiva.pop();
}
out<<nr_comp<<"\n";
//out<<"----";
for(int i = 1; i <= nr_comp; i++)
{
for(size_t j = 0; j < componente_conexe[i].size(); j++)
out<<componente_conexe[i][j]<<" ";
out<<"\n";
}
return 0;
}