Pagini recente » Cod sursa (job #76835) | Cod sursa (job #968887) | Cod sursa (job #949393) | Cod sursa (job #2356623) | Cod sursa (job #1378496)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
const int MAXN = 100002;
struct V{int index; int lowlink;};
vector<int> g[MAXN];
stack<int> st;
V v[MAXN];
bool in_stack[MAXN];
bool new_line[MAXN];
int sol[MAXN];
int nr_sol = 0;
int index = 0;
inline int Min(int a, int b)
{
if (a < b)
return a;
return b;
}
void scc(int x)
{
in_stack[x] = 1;
st.push(x);
v[x].index = ++index;
v[x].lowlink = index;
for (int i = 0; i < g[x].size(); i++)
{
if (v[g[x][i]].index == 0)
{
scc(g[x][i]);
v[x].lowlink = Min(v[x].lowlink, v[g[x][i]].lowlink);
}
else
if (in_stack[g[x][i]])
v[x].lowlink = Min(v[x].lowlink, v[g[x][i]].index);
}
if (v[x].index == v[x].lowlink)
{
++nr_sol;
new_line[sol[0]] = 1;
int t;
do
{
t = st.top();
st.pop();
sol[++sol[0]] = t;
in_stack[t] = 0;
} while (t != x);
}
}
int main()
{
FILE *in = fopen("ctc.in", "r");
FILE *out = fopen("ctc.out", "w");
int n, m;
fscanf(in, "%d%d", &n, &m);
for (int x, y; m > 0; m--)
{
fscanf(in, "%d%d", &x, &y);
g[x].push_back(y);
}
for (int i = 1; i <= n; i++)
if (v[i].index == 0)
scc(i);
fprintf(out, "%d\n", nr_sol);
for (int i = 1; i <= n; i++)
{
fprintf(out, "%d ", sol[i]);
if (new_line[i])
fprintf(out, "\n");
}
fprintf(out, "\n");
return 0;
}