Pagini recente » Cod sursa (job #659477) | Cod sursa (job #1265344) | Cod sursa (job #2549205) | Cod sursa (job #614806) | Cod sursa (job #1309721)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 102;
int N, M, top;
int st[MAX_N];
vector < int > v[MAX_N], w[MAX_N], a, component[MAX_N], sol, A, B, C, D;
bool OK;
bool vis[MAX_N], Edge[MAX_N][MAX_N], in[MAX_N], in_stack[MAX_N];
void DFS1(int x) {
vis[x] = 1;
for(int i = 0; i < (int) v[x].size(); ++i) {
int y = v[x][i];
if(!vis[y])
DFS1(y);
}
a.push_back(x);
}
void DFS2(int x, int nr) {
vis[x] = 1;
component[nr].push_back(x);
for(int i = 0; i < (int) w[x].size(); ++i) {
int y = w[x][i];
if(!vis[y])
DFS2(y, nr);
}
}
void DFS(int x) {
st[++top] = x;
vis[x] = in_stack[x] = 1;
for(int i = 0; i < (int) v[x].size(); ++i) {
if(OK)
return;
int y = v[x][i];
if(in_stack[y]) {
OK = 1;
while(st[top] != y)
A.push_back(st[top--]);
A.push_back(y);
reverse(A.begin(), A.end());
}
else if(in[y])
DFS(y);
}
in_stack[st[top--]] = 0;
}
void splitNodes() {
bool m[MAX_N];
B.clear();
C.clear();
D.clear();
for(int i = 1; i <= N; ++i)
m[i] = 0;
for(int i = 0; i < (int) A.size(); ++i)
m[A[i]] = 1;
for(int i = 1; i <= N; ++i)
if(in[i] && m[i] == 0) {
bool ok1 = 0, ok2 = 0;
for(int j = 0; j < (int) v[i].size() && !ok1; ++j)
if(m[v[i][j]])
ok1 = 1;
for(int j = 0; j < (int) w[i].size() && !ok2; ++j)
if(m[w[i][j]])
ok2 = 1;
if(ok1 && ok2)
B.push_back(i);
else if(ok1)
D.push_back(i);
else if(ok2)
C.push_back(i);
}
}
vector < int > solveComponent(vector < int > component) {
for(int i = 0; i < (int) component.size(); ++i)
in[component[i]] = 1;
for(int i = 0; i < (int) component.size() && A.size() == 0; ++i) {
top = 0;
for(int j = 1; j <= N; ++j)
vis[j] = in_stack[j] = 0;
DFS(component[i]);
}
do {
splitNodes();
if(B.size() > 0) {
bool ok = 0;
for(int j = 0; j + 1 < (int) A.size() && !ok; ++j) {
if(Edge[A[j]][B[0]] && Edge[B[0]][A[j + 1]]) {
ok = 1;
A.push_back(B[0]);
for(int k = A.size() - 1; k > j + 1; --k)
swap(A[k], A[k - 1]);
}
}
if(!ok)
A.push_back(B[0]);
}
else if(C.size() > 0) {
for(int j = 0; j < (int) D.size(); ++j)
if(Edge[C[0]][D[j]]) {
A.push_back(C[0]);
A.push_back(D[j]);
break;
}
}
} while(B.size() > 0 || C.size() > 0);
return A;
}
int main() {
ifstream f("plimbare.in");
ofstream g("plimbare.out");
f >> N;
M = N * (N - 1) / 2;
for(int i = 1; i <= M; ++i) {
int x, y;
f >> x >> y;
Edge[x][y] = 1;
v[x].push_back(y);
w[y].push_back(x);
}
for(int i = 1; i <= N; ++i)
if(!vis[i])
DFS1(i);
for(int i = 1; i <= N; ++i)
vis[i] = 0;
int n = 0;
for(int i = a.size() - 1; i >= 0; --i) {
if(vis[a[i]])
continue;
++n;
DFS2(a[i], n);
}
a.clear();
for(int i = 1; i <= n; ++i)
if(component[i].size() > a.size())
a = component[i];
sol = solveComponent(a);
g << sol.size() << "\n";
for(int i = 0; i < (int) sol.size(); ++i)
g << sol[i] << " ";
g << "\n";
f.close();
g.close();
return 0;
}