Pagini recente » Cod sursa (job #715090) | Cod sursa (job #1674373) | Cod sursa (job #1891937) | Cod sursa (job #511535) | Cod sursa (job #1122418)
#include <cstdio>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
const int NMAX = 102;
vector <short> G[NMAX], rec_s, ans;
stack <short> S;
bitset <NMAX> check;
short downlink[NMAX], order[NMAX], scc[NMAX], s, c, R;
void tarjan (const short &node) {
order[node] = downlink[node] = ++s;
S.push (node);
for (vector <short> :: iterator i = G[node].begin (); i != G[node].end (); ++i)
if (!order[*i]) {
tarjan (*i);
downlink[node] = min (downlink[node], downlink[*i]);
}
else
if (order[*i] != -1)
downlink[node] = min (downlink[node], downlink[*i]);
if (downlink[node] == order[node]) {
++c;
while (S.top () != node) {
scc[S.top ()] = c;
order[S.top ()] = -1;
S.pop ();
}
scc[node] = c;
order[node] = -1;
S.pop ();
}
}
void DFS () {
check[rec_s.back ()] = 1;
for (vector <short> :: iterator i = G[rec_s.back ()].begin (); i != G[rec_s.back ()].end (); ++i)
if (!check[*i]) {
if (scc[rec_s.back ()] == scc[*i]) {
rec_s.push_back (*i);
DFS ();
rec_s.pop_back ();
}
}
else
if (rec_s.size () > ans.size () && rec_s[0] == *i)
ans = rec_s;
}
int main () {
freopen ("plimbare.in", "r", stdin);
freopen ("plimbare.out", "w", stdout);
short N, M, a, b, i;
scanf ("%hd", &N);
M = (N * (N - 1)) >> 1;
while (M--) {
scanf ("%hd%hd", &a, &b);
G[a].push_back (b);
}
for (i = 1; i <= N; ++i)
if (!order[i])
tarjan (i);
for (i = 1; i <= N; ++i) {
rec_s.push_back (i);
DFS ();
rec_s.pop_back ();
check.reset ();
}
printf ("%d\n", ans.size ());
for (vector <short> :: iterator j = ans.begin (); j != ans.end (); ++j)
printf ("%hd ", *j);
}