Pagini recente » Cod sursa (job #2441999) | Cod sursa (job #2960847) | Cod sursa (job #367283) | Cod sursa (job #264274) | Cod sursa (job #470663)
Cod sursa(job #470663)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
const int NMAX = 100005;
const int ALB = 0;
const int NEGRU = 1;
const char in[] = "ctc.in";
const char out[] = "ctc.out";
template<class T>
T minx(T a, T b)
{
return ((a) < (b) ? (a) : (b));
}
typedef struct nod {
int vf;
struct nod * next;
} *PNOD, NOD;
PNOD L[NMAX];
int N, M, level, nrsol;
int color[NMAX], l[NMAX], niv[NMAX];
stack<int> st;
vector<int> t;
void Add(int i, int j)
{
PNOD p = new NOD;
p->vf = j;
p->next = L[i];
L[i] = p;
}
void DF(int nod)
{
PNOD p;
int q;
size_t j;
color[nod] = NEGRU;
niv[nod] = ++level;
l[nod] = level;
st.push(nod);
for (p = L[nod]; p; p = p->next)
if (!l[p->vf])
{
DF(p->vf);
l[nod] = minx(l[nod], l[p->vf]);
}
else if(color[p->vf] == NEGRU)
l[nod] = minx(l[nod], niv[p->vf]);
if (l[nod] == niv[nod])
{
++nrsol;
t.clear();
while (1)
{
t.push_back(q = st.top());
color[q] = ALB;
st.pop();
if (q == nod) break;
}
for (j = 0; j < t.size(); ++j)
printf("%d ", t[j]);
printf("\n");
}
}
int main(int argc, char **argv)
{
freopen(in, "r", stdin);
freopen(out, "w", stdout);
scanf("%d%d", &N, &M);
int i, j;
for ( ; M; --M)
{
scanf("%d%d", &i, &j);
Add(i, j);
}
printf(" \n");
for (i = 1; i <= N; ++i)
if (!l[i]) DF(i);
fseek(stdout, 0, SEEK_SET);
printf("%d", nrsol);
return 0;
}