Cod sursa(job #1309721)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 5 ianuarie 2015 23:09:54
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.78 kb
#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;
}