Pagini recente » Cod sursa (job #2197434) | Clasament baraj2017 | Cod sursa (job #107179) | Cod sursa (job #484209) | Cod sursa (job #729880)
Cod sursa(job #729880)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
#define maxn 100001
stack <int> s;
vector <int> a[maxn],comp[maxn];
int ins[maxn],jos[maxn],pos[maxn],p,nc,n,m;
void tarjan(int k){
pos[k]=p;
jos[k]=p;
s.push(k);
ins[k]=1;
p++;
int i,nod;
for(i=0;i<a[k].size();i++){
nod=a[k][i];
if(pos[nod]<0){
tarjan(nod);
if(jos[nod]<jos[k])
jos[k]=jos[nod];}
else
if(ins[nod]&&jos[nod]<jos[k])
jos[k]=jos[nod];}
if(pos[k]==jos[k]){
nc++;
do{
nod=s.top();
comp[nc-1].push_back(nod);
s.pop();
ins[nod]=0;}
while(nod!=k);}}
int main(){
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
int i,x,y;
for(i=1;i<=m;i++){
f>>x>>y;
a[x].push_back(y);}
for(i=1;i<=n;i++)
pos[i]=-1;
for(i=1;i<=n;i++)
if(pos[i]<0)
tarjan(i);
g<<nc<<"\n";
for(i=0;i<nc;i++){
for(x=0;x<comp[i].size();x++)
g<<comp[i][x]<<" ";
g<<"\n";}
f.close();
g.close();
return 0;}