Pagini recente » Cod sursa (job #3224214) | Cod sursa (job #1652156) | Cod sursa (job #1433616) | Cod sursa (job #2626410) | Cod sursa (job #778168)
Cod sursa(job #778168)
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
#define NMAX 100001
#define EMAX 200001
enum state {NEW, INSTACK, DONE};
int n, m;
int i, j, k, maxCol, index;
state s[NMAX];
vector<int> e[NMAX];
int c[NMAX], low[NMAX], t[NMAX];
int sol[NMAX], solSize;
stack<int> st;
void DFS(int node);
void Color(int node);
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d\n", &n, &m);
for (k = 1; k <= m; k++)
{
scanf("%d %d", &i, &j);
e[i].push_back(j);
}
for (k = 1; k <= n; k++)
if (s[k] == NEW)
DFS(k);
printf("%d\n", maxCol);
for (k = 1; k <= n; k++)
{
if (k > 1 && c[sol[k]] != c[sol[k-1]]) printf("\n");
printf("%d ", sol[k]);
}
return 0;
}
void DFS(int node)
{
if (s[node] != NEW) return;
s[node] = INSTACK;
t[node] = ++index;
low[node] = index;
st.push(node);
for (vector<int>::iterator it = e[node].begin(); it != e[node].end(); ++it)
if (s[*it] == NEW)
{
DFS(*it);
if (low[node] > low[*it]) low[node] = low[*it];
}
else if (s[*it] == INSTACK)
{
if (low[node] > low[*it]) low[node] = low[*it];
}
if (low[node] == t[node])
Color(node);
}
void Color(int node)
{
++maxCol;
while (st.top() != node)
{
int v = st.top();
s[v] = DONE;
c[v] = maxCol;
st.pop();
sol[++solSize] = v;
}
s[st.top()] = DONE;
c[st.top()] = maxCol;
sol[++solSize] = st.top();
st.pop();
}