Pagini recente » Rating Butacu Stefan (AltexStefan) | Cod sursa (job #448377) | Cod sursa (job #3193848) | Cod sursa (job #1545901) | Cod sursa (job #839568)
Cod sursa(job #839568)
#include <cstdio>
#include <vector>
#include <stack>
const int maxn = 100010;
using namespace std;
vector <int> g[maxn], v[maxn];
stack <int> tmp;
int nr;
char visited[maxn], in_stack[maxn];
int dfn[maxn], low[maxn];
int ticket;
void _pop(int node) {
int x;
do {
x = tmp.top(); tmp.pop();
v[nr].push_back(x) ;
in_stack[node] = 0;
} while(x != node);
++nr;
}
void tarjan(int node) {
dfn[node] = low[node] = ticket;
visited[node] = in_stack[node] = 1;
tmp.push(node);
ticket += 1;
for(vector <int> :: iterator it = g[node].begin(); it != g[node].end(); ++it) {
if(visited[*it] == 0) {
tarjan(*it);
low[node] = min(low[node], low[*it]);
}
else if(in_stack[*it])
low[node] = min(low[node], dfn[*it]);
}
if(low[node] == dfn[node]) {
//found a root of a strongly connected component
_pop(node);
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m, x, y;
for( scanf("%d %d\n", &n, &m); m--; ) {
scanf("%d %d\n", &x, &y);
g[x].push_back(y);
}
for(int i = 1; i <= n; ++i)
if(!visited[i]) tarjan(i);
printf("%d\n", nr);
for(int i = 0; i < nr; ++i) {
for(vector <int> :: iterator it = v[i].begin();it != v[i].end(); ++it)
printf("%d ", *it);
printf("\n");
}
return 0;
}