Pagini recente » Cod sursa (job #947499) | Cod sursa (job #3144836) | Cod sursa (job #582481) | Cod sursa (job #1868329) | Cod sursa (job #3275707)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX=100010;
int N,M,nrc;
vector<int>G[NMAX],GT[NMAX],
CTC[NMAX], ///CTC[i]=lista nodurilor din a i-a c.t.c
Post;///Lista nodurilor lui G i oridnea finalizarii acestora in pacurgerea DFS
bool viz[NMAX];
void citire() {
int x,y;
f>>N>>M;
while(M--) {
f>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void dfs(int vf) {
viz[vf]=1;///+
for(int x:G[vf]) {
if(viz[x]==0) {
dfs(x);
}
}
Post.push_back(vf);///s-a finalizat parcurgerea din vf
}
void dfsGT(int vf) {
viz[vf]=0;///-
CTC[nrc].push_back(vf);
for(int x:GT[vf]) {
if(viz[x]==1) {
dfsGT(x);
}
}
}
void componente() { ///Algoritmul Kosaraju-Sharir
int i;
for(i=1; i<=N; ++i) {
if(viz[i]==0) {
dfs(i);
}
}
for(i=Post.size()-1; i>=0; i--) {
if(viz[Post[i]]==1) {
nrc++;
dfsGT(Post[i]);
}
}
}
void afisare() {
g<<nrc<<'\n';
for(int i=1; i<=nrc; i++) {
for(int x:CTC[i]) {
g<<x<<' ';
}
g<<'\n';
}
}
int main() {
citire();
componente();
afisare();
f.close();
g.close();
return 0;
}