Mai intai trebuie sa te autentifici.
Cod sursa(job #611644)
Utilizator | Data | 2 septembrie 2011 15:39:32 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.19 kb |
#include<fstream>
#include<vector>
#define mx 200200
using namespace std;
vector<int> v[mx],stiva,solutie,stop;
int lnk[mx],vizitat[mx],indice[mx],n,nr=1;
void afis() {
int i,j=0,m=solutie.size();
ofstream out("ctc.out");
out<<stop.size()<<'\n';
for(i=0;i<m;i++)
{out<<solutie[i]<<" ";
if(stop[j]==i)
out<<'\n',j++;
}
out.close();
}
void DFS(int nod) {
int vecin,i,m=v[nod].size();
vizitat[nod]=1;
indice[nod]=nr;
lnk[nod]=nr++;
stiva.push_back(nod);
for(i=0;i<m;i++)
{vecin=v[nod][i];
if(!indice[vecin])
{DFS(vecin);lnk[nod]=min(lnk[nod],lnk[vecin]);}
else if(vizitat[vecin]) lnk[nod]=min(lnk[nod],lnk[vecin]);
}
if(lnk[nod]==indice[nod])
{solutie.push_back(stiva.back());
vizitat[stiva.back()]=0;
while(stiva.back()!=nod)
{stiva.pop_back();
vizitat[stiva.back()]=0;
solutie.push_back(stiva.back());
}
stiva.pop_back();
stop.push_back(solutie.size()-1);
}
}
void citire() {
int i,m,x,y;
ifstream in("ctc.in");
in>>n>>m;
for(i=0;i<m;i++)
{in>>x>>y;
v[x].push_back(y);
}
in.close();
}
int main() {
int i;
citire();
for(i=1;i<=n;i++)
if(!indice[i])
DFS(i);
afis();
return 0;
}