Pagini recente » Cod sursa (job #3278524) | Cod sursa (job #3293722) | Cod sursa (job #3293635) | Cod sursa (job #3293884) | Cod sursa (job #236041)
Cod sursa(job #236041)
/*
Componente tare conexe
Alg. Kosaraju-Sharir
*/
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
const int NMAX=100001;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> G[NMAX],GT[NMAX];
int N,M,s[NMAX],nr;
bitset<NMAX> viz;
vector< vector<int> > C;
int nc;
void DF(int vf){
vector<int>::iterator it;
viz[vf]=1;
for (it=G[vf].begin();it!=G[vf].end();++it)
if (!viz[*it]) DF(*it);
s[++nr]=vf;
}
vector<int> aux;
void DFT(int vf){
vector<int>::iterator it;
viz[vf]=0;
aux.push_back(vf);
for (it=GT[vf].begin();it!=GT[vf].end();++it)
if (viz[*it]) DFT(*it);
}
int main(){
int i,j;
vector<int>::iterator it;
fin>>N>>M;
while (M--){
fin>>i>>j;
G[i].push_back(j);
GT[j].push_back(i);
}
for (i=1;i<=N;++i)
if (!viz[i]) DF(i);
for (i=N;i;i--)
if (viz[s[i]]){
++nc;
aux.clear();
DFT(s[i]);
C.push_back(aux);}
fout<<nc<<'\n';
for (i=0;i<nc;++i){
for (it=C[i].begin();it!=C[i].end();++it)
fout<<*it<<' ';
fout<<'\n';}
return 0;
}