Pagini recente » Cod sursa (job #1574442) | Cod sursa (job #2098942) | Cod sursa (job #1780331) | Cod sursa (job #2714213) | Cod sursa (job #2383347)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("in.in");
ofstream fo("out.out");
const int NMAX = 1e5 + 5;
int n, m;
vector <int> G[NMAX], H[NMAX];
bool viz[NMAX];
int stiva[NMAX], k;
int nrComp, comp[NMAX];
vector <int> bat[NMAX];
void dfs1(int nod)
{
viz[nod] = 1;
for (auto v: G[nod])
if (!viz[v])
dfs1(v);
stiva[++k] = nod;
}
void dfs2(int nod)
{
bat[nrComp].push_back(nod);
comp[nod] = nrComp;
for (auto v: H[nod])
if (!comp[v])
dfs2(v);
}
int main()
{
fi >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
fi >> u >> v;
G[u].push_back(v);
H[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs1(i);
for (int i = 1; i <= n; i++)
if (!viz[i])
{
fo << 0;
return 0;
}
while (k > 0)
{
int nod = stiva[k--];
nrComp++;
dfs2(nod);
}
int cntr = 0;
vector <int> rez;
for (int i = 1; i <= nrComp; i++)
{
bool rad = 1, fr = 1;
for (auto nod: bat[i])
{
for (auto v: G[nod])
if (comp[v] != comp[nod])
fr = 0;
for (auto v: H[nod])
if (comp[v] != comp[nod])
rad = 0;
}
if (rad)
cntr++;
if (fr)
for (auto nod: bat[i])
rez.push_back(nod);
}
if (cntr <= 1)
{
fo << rez.size() << "\n";
for (auto x: rez)
fo << x << " ";
}
return 0;
}