Pagini recente » Istoria paginii utilizator/uscostin | Istoria paginii runda/oni_cl8 | Cod sursa (job #1582746) | Cod sursa (job #1571921) | Cod sursa (job #1139445)
#include <cstdio>
#include <vector>
#include <stack>
#define minim(a,b) (a<b)?(a):(b)
#define nmax 50005
using namespace std;
vector <int> g[nmax];
vector <int> r[nmax];
stack <int> stk;
int low[nmax];
int index[nmax];
bool viz[nmax];
int n,m;
int nr;
int tarjan(int start) {
stk.push(start);
low[start] = index[start] = stk.size();
viz[start] = true;
for (vector <int> :: iterator it = g[start].begin(); it != g[start].end();it++) {
if (viz[*it]) low[start] = minim(low[start],low[*it]);
else low[start] = tarjan(*it);
}
if (low[start] == index[start]) {
nr++;
while (stk.size() >= low[start]) {
r[nr].push_back(stk.top());
stk.pop();
}
}
return low[start];
}
int main() {
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for (int i=1;i<=m;i++) {
int a,b;
scanf("%d %d",&a,&b);
g[a].push_back(b);
}
for (int i=1;i<=n;i++) if (!viz[i]) tarjan(i);
printf("%d\n",nr);
for (int i=1;i<=nr;i++) {
for (vector <int> ::iterator it = r[i].begin();it != r[i].end();it++) printf("%d ",*it);
printf("\n");
}
}