Pagini recente » Istoria paginii runda/test_icrisop_2/clasament | Istoria paginii runda/lasm_21_02_2025_clasa11/clasament | Profil MilenaPOPA | simulareaii | Cod sursa (job #1707071)
# include <bits/stdc++.h>
using namespace std;
const int Nmax = 100000 + 5;
int n, m, N = 0, S = 0, x, y;
int st[Nmax], sol[Nmax];
bool ap[Nmax];
vector <int> G1[Nmax], G2[Nmax];
void read()
{
for (int i = 1; i <= m; ++i)
{
scanf("%d %d\n", &x, &y);
G1[x].push_back(y), G2[y].push_back(x);
}
}
void DFS (int node)
{
ap[node] = true;
for (int i = 0; i < G1[node].size(); ++i)
if (!ap[G1[node][i]]) DFS(G1[node][i]);
st[++N] = node;
}
void DFT(int node, bool afis)
{
ap[node] = true;
if (afis == true) printf("%d ", node);
for (int i = 0; i < G2[node].size(); ++i)
if (!ap[G2[node][i]]) DFT(G2[node][i], afis);
}
int main ()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int i;
scanf("%d %d\n", &n, &m);
read();
for (i = 1; i <= n; ++i)
if (!ap[i]) DFS(i);
memset(ap, false, sizeof(ap));
int nr = 0;
for (i = n; i >= 1; --i)
{
if (!ap[st[i]])
{
DFT(st[i], false);
++nr;
}
}
printf("%d\n", nr);
memset(ap, false, sizeof(ap));
for (i = n; i >= 1; --i)
{
if (!ap[st[i]])
{
DFT(st[i], true);
printf("\n");
}
}
return 0;
}