Pagini recente » Cod sursa (job #2223146) | Cod sursa (job #2754968) | Cod sursa (job #1657686) | Cod sursa (job #686153) | Cod sursa (job #638890)
Cod sursa(job #638890)
#include <fstream>
#define nmax 100011
#include <deque>
#include <vector>
#include <bitset>
using namespace std;
vector<int> gf[nmax];
deque<int> Dq;
vector<int> sol[nmax];
int nr_ctc;
int n,m;
int index= 0;
int id[nmax], low_link[nmax];
bitset<nmax> viz;
ifstream f("ctc.in");
ofstream g("ctc.out");
void citeste(){
f>>n>>m;
for(int i=1; i<=m; ++i){
int x,y;
f>>x>>y;
gf[x].push_back(y);
}
}
int minim(int a, int b){
if (a > b) return b;
return a;
}
void tarjan(int nod){
++index;
id[nod] = index;
low_link[nod] = index;
Dq.push_back(nod);
viz[nod] = 1;
for(unsigned i=0; i < gf[nod].size(); ++i){
int vecin = gf[nod][i];
if (id[vecin] == -1){
tarjan( vecin );
low_link[nod] = minim(low_link[nod], low_link[vecin]);
}else if (viz[vecin] == 1){
low_link[nod] = minim(low_link[nod], id[vecin]);
}
}
if (low_link[nod] == id[nod]){
int w = Dq.back();
Dq.pop_back();
viz[w] = 0;
++nr_ctc;
sol[nr_ctc].push_back(w);
while (w != nod){
w = Dq.back();
Dq.pop_back();
viz[w] = 0;
sol[nr_ctc].push_back(w);
}
}
}
void rezolva(){
for(int i=0; i<=n; ++i) id[i] = -1;
for(int i=1; i<=n; ++i){
if (id[i] == -1)
tarjan(i);
}
}
void scrie(){
g<<nr_ctc<<"\n";
for(int i=1; i<=nr_ctc; ++i){
for(unsigned j=0; j < sol[i].size(); ++j)
g<<sol[i][j]<<" ";
g<<"\n";
}
}
int main(){
citeste();
rezolva();
scrie();
f.close();
g.close();
return 0;
}