Pagini recente » Cod sursa (job #1880980) | Cod sursa (job #1601460) | Cod sursa (job #234831) | Cod sursa (job #983731) | Cod sursa (job #843757)
Cod sursa(job #843757)
#include <stdio.h>
#include <vector>
#include <stack>
#define MAXN 100001
using namespace std;
int M,N;
vector<int> vecini[MAXN];
vector<int> veciniT[MAXN];
stack<int> st;
vector<vector<int> > componente;
bool visited[MAXN];
void dfs(int nod)
{
visited[nod] = true;
vector<int>::iterator it;
for(it = vecini[nod].begin() ; it != vecini[nod].end(); it++){
if( !visited[*it] )
dfs(*it);
}
st.push(nod);
}
void dfsT(int nod, vector<int> *solution)
{
solution->push_back(nod);
visited[nod] = true;
vector<int>::iterator it;
for(it = veciniT[nod].begin() ; it != veciniT[nod].end(); it++){
if( !visited[*it] )
dfsT(*it, solution);
}
}
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);
veciniT[right].push_back(left);
}
for(i=1;i<=N;i++){
if( !visited[i] )
dfs(i);
}
for(i=1;i<=N;i++)
visited[i] = false;
int nod;
while( !st.empty() ){
nod = st.top();
st.pop();
if( !visited[nod] ){
vector<int> solutie;
dfsT(nod, &solutie);
componente.push_back(solutie);
}
}
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;
}