제출 #230738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230738		nicolaalexandra	Potemkin cycle (CEOI15_indcyc)	C++14	20 / 100	1095 ms	9720 KiB

indcyc

#include <bits/stdc++.h>
#define DIM 1010
using namespace std;

set <int> L[DIM],s;
deque <int> d,sol;
vector <pair<int,int> > mch;
int n,m,x,y,i,j,ok;
int level[DIM];

void dfs (int nod, int tata){
    if (ok)
        return;

    d.push_back(nod);
    s.insert(nod);
    level[nod] = 1 + level[tata];

    for (auto vecin : L[nod]){
        if (level[vecin])
            continue;

        /// verific daca are muchii de intoarcere
        int maxi = 0, poz = 0;
        for (auto it : L[vecin]){
            if (it != nod && s.find(it) != s.end()){ /// muchie de intoarcere
                if (level[it] > maxi)
                    maxi = level[it], poz = it;
            }
        }

        if (!maxi)
            dfs (vecin,nod);
        else {
            if (level[nod] + 1 - level[poz] + 1 >= 4){
                /// am gasit un ciclu bun
                sol.push_back(vecin);
                while (d.back() != poz){
                    sol.push_back(d.back());
                    d.pop_back();
                }
                sol.push_back(poz);
                ok = 1;
            }
        }
    }


    /// am terminat cu nod, trb sa l sterg
    d.pop_back();
    s.erase(nod);
}
int main (){

    //ifstream cin ("date.in");
   // ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=m;i++){
        cin>>x>>y;
        L[x].insert(y);
        L[y].insert(x);
    }

    for (i=1;i<=n;i++){
        d.clear(), s.clear();
        memset (level,0,sizeof level);
        ok = 0;
        dfs (i,0);
        if (ok){
            for (auto it : sol)
                cout<<it<<" ";
            return 0;
        }
    }


    cout<<"no";

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10