Pagini recente » Cod sursa (job #567838) | Cod sursa (job #1235301) | Cod sursa (job #255610) | Cod sursa (job #72606) | Cod sursa (job #843767)
Cod sursa(job #843767)
#include <stdio.h>
#include <vector>
#include <stack>
#define MAXN 100001
using namespace std;
int M,N;
vector<int> vecini[MAXN];
stack<int> st;
vector<vector<int> > componente;
int timp[MAXN];
int lowlink[MAXN];
int timp_curent = 1;
int tarjanel_id[MAXN];
int tarjanel_id_count = 0;
int min( int x, int y)
{
if( x < y )
return x;
else
return y;
}
void tarjan(int nod)
{
timp[nod] = timp_curent++;
lowlink[nod] = nod;
tarjanel_id[nod] = tarjanel_id_count;
st.push(nod);
vector<int>::iterator it;
for(it=vecini[nod].begin(); it!=vecini[nod].end();it++){
if( timp[*it] == 0 ){
tarjan(*it);
if( timp[lowlink[*it]] < timp[lowlink[nod]] )
lowlink[nod] = lowlink[*it];
}
else if( tarjanel_id[*it] == tarjanel_id_count ){
if( timp[lowlink[*it]] < timp[lowlink[nod]] )
lowlink[nod] = lowlink[*it];
}
}
if( lowlink[nod] == nod ){
vector<int> solutie;
solutie.push_back(nod);
int i;
while( (i=st.top()) != nod){
solutie.push_back(i);
st.pop();
}
st.pop();
componente.push_back(solutie);
}
}
int main(int argc, char* argv[])
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&N,&M);
int i, left, right;
for(i=0;i<M;i++){
scanf("%d %d",&left,&right);
vecini[left].push_back(right);
}
for(i=1;i<=N;i++){
tarjanel_id_count++;
if( timp[i] == 0 )
tarjan(i);
}
vector<vector<int> >::iterator itsol;
vector<int>::iterator itval;
printf("%d\n",componente.size());
for(itsol=componente.begin(); itsol != componente.end(); itsol++){
for(itval = itsol->begin(); itval != itsol->end(); itval++){
printf("%d ",*itval);
}
printf("\n");
}
return 0;
}