Pagini recente » Cod sursa (job #86923) | Cod sursa (job #609383) | Cod sursa (job #1147086) | Cod sursa (job #1396528) | Cod sursa (job #2928473)
#include <iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
bool vizitat[100001];
vector<int> graf[100001], grafinv[100001], ctc[100001];
stack<int> s; //pastreaza ordinea in care am apelat dfs pe noduri
int n, m, a, b, nr;
void citire(){
fin>>n>>m;
for(int i=0;i<m;i++){
fin>>a>>b;
graf[a].push_back(b);
grafinv[b].push_back(a);
}
}
void dfs(int nod){
s.push(nod);
vizitat[nod] = true;
for(auto nodd : graf[nod])
if(vizitat[nodd] == false)
dfs(nodd);
}
void dfsinv(int nod){
vizitat[nod]=false;
ctc[nr].push_back(nod);
for (auto nodd : grafinv[nod])
if (vizitat[nodd] == true)
dfsinv(nodd);
}
void afisare(){
fout<<nr<<"\n";
for(int i = 1; i<=nr; i++){
for(int j = 0; j < ctc[i].size(); j++)
fout<<ctc[i][j]<<" ";
fout<<"\n";
}
}
int main()
{
citire();
nr=0; //nr de ctc-uri
for(int i=1; i<=n; i++){
if(vizitat[i] == false)
dfs(i);
}
while(!s.empty()){
int nod=s.top();
s.pop();
if(vizitat[nod]==true){
nr++;
dfsinv(nod);
}
}
afisare();
return 0;
}