Pagini recente » Cod sursa (job #2803603) | Cod sursa (job #1573126) | Cod sursa (job #1175827) | Cod sursa (job #167542) | Cod sursa (job #586665)
Cod sursa(job #586665)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int MAX_NODURI = 100004;
int nNoduri, nMuchii;
vector<int> grafNormal[MAX_NODURI], grafTranspus[MAX_NODURI];
vector< vector<int> > solution;
int used[MAX_NODURI];
void read_input(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&nNoduri,&nMuchii);
for (int i=0; i<nMuchii; ++i){
static int x, y;
scanf("%d%d",&x,&y);
grafNormal[x].push_back(y);
grafTranspus[y].push_back(x);
}
}
void dfs (const int nod, vector<int>* graf, int step){
vector<int>::iterator it;
used[nod] = step;
if (step == 2)
solution[solution.size()-1].push_back(nod);
for(it = graf[nod].begin(); it != graf[nod].end(); ++it){
if (used[*it] == step-1)
dfs(*it,graf,step);
}
}
void solve(){
vector<int> emptyVector;
for (int i=1; i<=nNoduri; ++i){
if (used[i]!=2){
solution.push_back(emptyVector);
dfs(i,grafNormal, 1);
dfs(i,grafTranspus, 2);
}
}
}
void print_output(){
printf("%d\n",solution.size());
for (int i=0; i<solution.size(); ++i){
for(int j=0; j<solution[i].size(); ++j)
printf("%d ",solution[i][j]);
printf("\n");
}
}
int main()
{
read_input();
solve();
print_output();
return 0;
}