Pagini recente » Cod sursa (job #67222) | Cod sursa (job #1655597) | Cod sursa (job #2164365) | Cod sursa (job #2792982) | Cod sursa (job #470428)
Cod sursa(job #470428)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define ALB 0
#define GRI 1
using namespace std;
const int NMAX = 100005;
const char in[] = "ctc.in";
const char out[] = "ctc.out";
typedef struct nod {
int vf;
struct nod *next;
} *PNOD, NOD;
PNOD L[NMAX];
void Add(int i, int j)
{
PNOD p = new NOD;
p->vf = j;
p->next = L[i];
L[i] = p;
}
stack<int> st;
int level;
int l[NMAX], niv[NMAX], sel[NMAX], tata[NMAX];
int N, M, nrsol;
void DF(int);
template <class T>
T minx(T a, T b)
{
return a < b ? a : b;
}
int main(void)
{
freopen (in, "r", stdin);
freopen(out, "w", stdout);
scanf("%d%d", &N, &M);
int i;
size_t j;
for ( ; M; --M)
{
scanf ("%d%d", &i, &j);
Add(i, j);
}
printf(" \n");
for (i = 1; i <= N; ++i)
if (sel[i] == ALB)
{
DF(i);
level = 0;
}
fseek(stdout, 0, SEEK_SET);
printf("%d", nrsol);
return 0;
}
void DF(int nod)
{
niv[nod] = ++level;
l[nod] = level;
sel[nod] = GRI;
st.push(nod);
PNOD p;
int x;
for (p = L[nod]; p; p = p->next)
{
if (sel[p->vf] == ALB)
{
DF(p->vf);
l[nod] = minx(l[nod], l[p->vf]);
}
else if (sel[nod] == GRI)
l[nod] = minx(l[nod], niv[p->vf]);
}
if (l[nod] == niv[nod])
{
++nrsol;
while(1)
{
x = st.top();
printf("%d ", x);
st.pop();
if (x == nod) break;
}
printf("\n");
}
}