Pagini recente » Cod sursa (job #2520877) | Cod sursa (job #3209410) | Cod sursa (job #1843510) | Cod sursa (job #2161051) | Cod sursa (job #778157)
Cod sursa(job #778157)
#include <stdio.h>
#include <vector>
using namespace std;
#define NMAX 100001
#define EMAX 200001
enum color { NEW, DISCOVERED, PROCESSED };
int n, m;
int i, j, k, colMax;
color s[NMAX];
vector<int> e[NMAX], eb[NMAX];
int c[NMAX];
int sol[NMAX], numSol;
int st[NMAX], stSize;
void DFS(int node);
void DFSB(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);
eb[j].push_back(i);
}
for (k = 1; k <= n; k++)
if (s[i] == NEW)
DFS(k);
for (k = 1; k <= n; s[k] = NEW, k++);
for (k = n; k >= 1; k--)
if (s[st[k]] == NEW)
{
colMax++;
DFSB(st[k]);
}
printf("%d\n", colMax);
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] = DISCOVERED;
for (vector<int>::iterator it = e[node].begin(); it != e[node].end(); ++it)
if (s[*it] == NEW)
DFS(*it);
stSize++;
st[stSize] = node;
s[node] = PROCESSED;
}
void DFSB(int node)
{
if (s[node] != NEW) return;
s[node] = DISCOVERED;
c[node] = colMax;
numSol++;
sol[numSol] = node;
for (vector<int>::iterator it = eb[node].begin(); it != eb[node].end(); ++it)
if (s[*it] == NEW)
DFSB(*it);
s[node] = PROCESSED;
}