Pagini recente » Cod sursa (job #503972) | Cod sursa (job #608170) | Cod sursa (job #3268602) | Cod sursa (job #1277933) | Cod sursa (job #1492310)
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
int v[100005];
int ll[100005];
bool ins[100005];
vector<vector<int>> T;
struct node{
node *next;
int inf;
};
node *L[100005];
void add(node *&start, int inf) {
node *one = new node;
one->inf = inf;
one->next = start;
start = one;
}
stack<int> s;
int nr;
void dfs(int in) {
nr ++;
v[in] = nr;
ll[in] = nr;
s.push(in);
ins[in] = true;
for(node *p = L[in]; p; p = p->next) {
if(!v[p->inf]) {
dfs(p->inf);
ll[in] = min(ll[in], ll[p->inf]);
}
else if(ins[p->inf]) {
ll[in] = min(ll[in], ll[p->inf]);
}
}
if(v[in] == ll[in]) {
vector<int> ans;
ans.clear();
int i;
do {
i = s.top();
s.pop();
ans.push_back(i);
ins[i] = false;
}
while(i != in);
T.push_back(ans);
}
}
int main()
{
FILE *f = fopen("ctc.in", "r");
FILE *g = fopen("ctc.out", "w");
fscanf(f, "%d %d", &n, &m);
for(int i = 1; i <= m; i ++) {
fscanf(f, "%d %d", &x, &y);
add(L[x], y);
}
for(int i = 1; i <= n; i ++) {
if(!v[i]) {
dfs(i);
}
}
fprintf(g, "%d\n", T.size());
for(int j = 0; j < T.size(); j ++) {
for(int i = 0; i < T[j].size(); i ++)
fprintf(g, "%d ", T[j][i]);
fprintf(g, "\n");
}
return 0;
}