Pagini recente » Cod sursa (job #2341813) | Cod sursa (job #2819457) | Cod sursa (job #2957337) | Cod sursa (job #435557) | Cod sursa (job #300780)
Cod sursa(job #300780)
#include <cstdio>
#include <cstring>
#include <list>
#include <stack>
using namespace std;
#define pb push_back
const int MAXN = 100010;
int n, nr;
list<int> vecini[MAXN];
list<int> vecinit[MAXN];
int sel[MAXN];
stack<int> st;
stack<int> st2;
list<int> ctc[MAXN];
void read();
void solve();
void write();
void dfs(int);
void dfst(int);
int main()
{
read();
solve();
write();
return 0;
}
void dfs(int nod)
{
st.push(nod);
list<int>::iterator it = vecini[nod].begin(), sfarsit = vecini[nod].end();
for (; it != sfarsit; ++it)
{
if (!sel[*it])
{
sel[*it] = 1;
dfs(*it);
}
}
}
void dfs2(int nod)
{
ctc[nr].pb(nod);
list<int>::iterator it = vecinit[nod].begin(), sfarsit = vecinit[nod].end();
for (; it != sfarsit; ++it)
{
if (!sel[*it])
{
sel[*it] = 1;
dfs2(*it);
}
}
}
void solve()
{
nr = 0;
int i;
for (i = 1; i <= n; ++i)
{
if (!sel[i])
{
sel[i] = 1;
dfs(i);
for (; !st.empty(); st.pop())
{
st2.push(st.top());
}
}
}
memset(sel, 0, sizeof(sel));
for (; !st2.empty(); st2.pop())
{
i = st2.top();
if (!sel[i])
{
++nr;
sel[i] = 1;
dfs2(i);
}
}
}
void read()
{
int i, m, x, y;
FILE *fin = fopen("ctc.in", "r");
fscanf(fin, "%d%d", &n, &m);
for (i = 1; i <= m; ++i)
{
fscanf(fin, "%d%d", &x, &y);
vecini[x].pb(y);
vecinit[y].pb(x);
}
fclose(fin);
}
void write()
{
int i;
list<int>::iterator it, sfarsit;
FILE *fout = fopen("ctc.out", "w");
fprintf(fout, "%d\n", nr);
for (i = 1; i <= nr; ++i)
{
sfarsit = ctc[i].end();
for (it = ctc[i].begin(); it != sfarsit; ++it)
{
fprintf(fout, "%d ", *it);
}
fprintf(fout, "\n");
}
fclose(fout);
}