Pagini recente » Clasament fminostress10simulare | Istoria paginii runda/a_b/clasament | Cod sursa (job #1653991) | Cod sursa (job #1572180) | Cod sursa (job #771629)
Cod sursa(job #771629)
#include <cassert>
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
const int nmax=100000;
//int n2;
int ind, nsol;
bool in_st[nmax+1];
int idx[nmax+1], ll[nmax+1];
stack <int> st;
vector <int> g[nmax+1], vsol[nmax];
void dfs(int x){
++ind;
idx[x]=ind;
ll[x]=ind;
st.push(x); in_st[x]=1;
/*fprintf(stderr, "\n%d...............idx[%d]=%d\n", x, x, ind);
for (int i=1; i<=n2; ++i){
fprintf(stderr, "%d ", in_st[i]);
}*/
for (vector <int>::iterator it=g[x].begin(); it!=g[x].end(); ++it){
if (!idx[*it]){
dfs(*it);
if (ll[*it]<ll[x]){
ll[x]=ll[*it];
}
}else if (in_st[*it]){
if (ll[*it]<ll[x]){
ll[x]=ll[*it];
}
}
/*if (x==8&& (*it==7)){
fprintf(stderr, "confirmed");
}*/
}
//fprintf(stderr, "\n%d..................ll[%d]=%d\n", x, x, ind);
if (idx[x]==ll[x]){
//fprintf(stderr, "\n--->%d\n", x);
int node;
do{
node=st.top();
st.pop(); in_st[node]=0;
vsol[nsol].push_back(node);
}while (x!=node);
++nsol;
}
}
int main(){
int n, m;
assert(freopen("ctc.in", "r", stdin));
assert(scanf(" %d %d ", &n, &m));
//n2=n;
for (; m; --m){
int x, y;
assert(scanf(" %d %d ", &x, &y));
g[x].push_back(y);
/*if (x==8&& y==7){
fprintf(stderr, "conf2");
}*/
}
for (int i=1; i<=n; ++i){
if (!idx[i]){
//fprintf(stderr, "%d\n", i);
dfs(i);
}
}
assert(freopen("ctc.out", "w", stdout));
printf("%d\n", nsol);
for (int i=0; i<nsol; ++i){
for (vector <int>::iterator it=vsol[i].begin();
it!=vsol[i].end(); ++it){
printf("%d ", *it);
}
printf("\n");
}
return 0;
}