Pagini recente » Cod sursa (job #2423000) | Cod sursa (job #3271964) | Cod sursa (job #60001) | Cod sursa (job #3275203) | Cod sursa (job #2937905)
//Complexitate: O(N+M)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int nrTotalComponente = 0;
int arrayNoduri[10000]; //pentru afisarea finala
int pozitiiDeNewline[10000];//pentru a stii cand trec la urnmatoarea CTC
int index;
void DFS1(int i,vector<int>& visited,stack<int>& stiva, vector<vector<int>>& listaAdiacenta) // parcurgere DFS pe graful normal
{
visited[i]=true;
for(int j: listaAdiacenta[i]) //parcurgem folosind DFS din fiecare nod
if(visited[j]==false)
DFS1(j,visited,stiva,listaAdiacenta);
stiva.push(i); //cand finalizam o parcurgere DFS, punem nodul pe stiva , conform alg lui Kosaraju
}
void DFS2(int i,vector<int>& visited, vector<vector<int>>& listaReversed) //DFS pe graful transpus
{
arrayNoduri[index]=i; // i-ul primit ca parametru este chiar nodul pe care trebuie sa il afisam
// pentru a respecta ordinea afisarii din cerinta, salvez toate valorile, in ordinea in care trebuie afisate
// in array-ul arrayNoduri
index++;
visited[i] = true;
for(int j: listaReversed[i])
if(!visited[j])
DFS2(j,visited,listaReversed);
}
void cautareCTC(vector<vector<int>>& listaAdiacenta, vector<vector<int>>& listaReversed, int n)
{
stack<int> stiva; //stiva pentru prima parcurgere DFS
vector<int> visited(n+1,0); //pentru nodurile vizitate
for(int i=1;i<n+1;++i)
if(!visited[i])
DFS1(i,visited,stiva,listaAdiacenta); //aplicam DFS pe nodurile nevizitate pentru a incarca stiva
for(int i=1;i<n+1;++i)
visited[i] = false; //resetam array-ul de noduri vizitate pentru a doua parcurgere
// cout<<"componente:\n";
while(!stiva.empty())
{
int curr = stiva.top();
stiva.pop(); //extragem primul element din stiva
if(visited[curr]==0)
{
DFS2(curr,visited,listaReversed); //daca nodul e nevizitat aplicam DFS pe graful transpus din acel nod
// cout<<index<<"\n";
pozitiiDeNewline[index]=1; //unde va aparea valoarea 1 in acest array, acolo o sa dam newLine la afisare
nrTotalComponente++;
}
}
// fout<<nrTotalComponente<<"\n";
}
int main()
{
int n,m;
fin>>n>>m;
vector<vector<int>> listaAdiacenta(n+1), listaReversed(n+1);
for(int i=0;i<n;i++)
arrayNoduri[i]=-1;
for(int i=0;i<n;i++)
pozitiiDeNewline[i]=-1;
int x,y;
while(m--){
fin>>x>>y;
listaAdiacenta[x].push_back(y);
listaReversed[y].push_back(x);
}
cautareCTC(listaAdiacenta, listaReversed, n);
fout<<nrTotalComponente<<'\n'; //mai intai afisam nr de componente
for(int i=0;i<index;i++)
{
if(pozitiiDeNewline[i]==-1)
fout<<arrayNoduri[i]<<" "; //daca pozitiiDeNewline==-1 , inca suntem la aceeasi componenta
else if(pozitiiDeNewline[i]==1)
fout<<"\n"<<arrayNoduri[i]<<" "; //daca pozitiiDeNewline==1, am trecut la urmatoarea componenta
}
// for(int i=0;i<=index;i++)
// cout<<pozitiiDeNewline[i]<<" ";
return 0;
}