Pagini recente » Cod sursa (job #2196700) | Cod sursa (job #2378442) | Cod sursa (job #546634) | Cod sursa (job #2307720) | Cod sursa (job #2971533)
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int N = 100000;
string file = "matroid";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
vector <int> succesori[N+1], predecesori[N+1], sir;
vector <vector <int> > conexe;
bitset<N + 1>viz;
void dfs(int x)
{
viz[x] = 1;
for (int y : succesori[x])
{
if (!viz[y])
{
dfs(y);
}
}
sir.push_back(x);
}
void dfs_t(int x)
{
viz[x] = 0;
conexe[conexe.size() - 1].push_back(x);
for (int y : predecesori[x])
{
if (viz[y])
{
dfs_t(y);
}
}
}
int main()
{
int n,m,x,y;
cin >> n >> m;
while (m)
{
m--;
cin >> x >> y;
succesori[x].push_back(y);
predecesori[y].push_back(x);
}
int ok = 0;
for (int i = 1; i <= n; i++)
{
if (!viz[i])
{
dfs(i);
}
if (predecesori[i].size() == 0)
{
if (ok)
{
cout << 0;
return 0;
}
ok = i;
}
}
if (ok)
{
cout << ok;
return 0;
}
reverse(sir.begin(), sir.end());
for (int x : sir)
{
if (viz[x])
{
dfs_t(x);
}
}
cout << conexe[0].size() << '\n';
for (int x : conexe[0])
{
cout << x << '\n';
}
}