Pagini recente » Cod sursa (job #939644) | Cod sursa (job #881583) | Cod sursa (job #1527501) | Cod sursa (job #2876513) | Cod sursa (job #2435417)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#define NMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
list<int> G[NMAX];
int index[NMAX], min_reach[NMAX], ct;
bool viz[NMAX];
stack<int> st;
list<int> cc[NMAX];
void connect(int x){
int y;
index[x] = min_reach[x] = ++index[0];
viz[x] = 1;
st.push(x);
list<int>::iterator it;
for(it = G[x].begin(); it != G[x].end(); it++){
y = *it;
if(!index[y]){
connect(y);
min_reach[x] = min(min_reach[x], min_reach[y]);
}
else if(viz[y]){
min_reach[x] = min(min_reach[x], index[y]);
}
}
if(index[x] == min_reach[x]){
ct++;y = 0;
while(y != x){
y = st.top();
st.pop(); viz[y] = 0;
cc[ct].push_back(y);
}
}
}
int main()
{
int n, m, i, x, y;
fin >> n >> m;
for(i = 1; i <= m; i++){
fin >> x >> y;
G[x].push_back(y);
}
index[0] = 0;
for(i = 1; i <= n; i++)
if(!index[i]) connect(i);
fout << ct << "\n";
for(i = 1; i <= ct; i++){
while(!cc[i].empty()){
fout << cc[i].back() << " ";
cc[i].pop_back();
}
fout << "\n";
}
return 0;
}