Pagini recente » Cod sursa (job #1052394) | Cod sursa (job #274898) | Cod sursa (job #1609438) | Cod sursa (job #2170456) | Cod sursa (job #2720725)
#include <fstream>
#include <vector>
#include <queue>
#define N 100005
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m;
vector<vector<int> > graf(N), grafInv(N), rez;
vector<int> sortare;
queue<int> coada;
bool vizitat[N];
void sortareTopologica(){
int nod = coada.front();
coada.pop();
vizitat[nod] = 1;
for(unsigned int i = 0; i < graf[nod].size(); ++i)
if(!vizitat[graf[nod][i]]){
coada.push(graf[nod][i]);
sortareTopologica();
}
sortare.push_back(nod);
}
void kosaraju(){
int nod = coada.front();
coada.pop();
vizitat[nod] = 0;
rez[rez.size() - 1].push_back(nod);
for(unsigned int i = 0; i < grafInv[nod].size(); ++i)
if(vizitat[grafInv[nod][i]]){
coada.push(grafInv[nod][i]);
kosaraju();
}
}
int main()
{
in>>n>>m;
for(int i = 1; i <= m; ++i){
int x, y;
in>>x>>y;
graf[x].push_back(y);
grafInv[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
if(!vizitat[i]){
coada.push(i);
sortareTopologica();
}
while(!coada.empty())coada.pop();
vector<int> aux;
for(int i = n - 1; i >= 0; --i)
if(vizitat[sortare[i]]){
rez.push_back(aux);
coada.push(sortare[i]);
kosaraju();
}
out<<rez.size()<<'\n';
for(unsigned int i = 0; i < rez.size(); ++i){
for(unsigned int j = 0; j < rez[i].size(); ++j)
out<<rez[i][j]<<" ";
out<<'\n';
}
in.close();
out.close();
return 0;
}