제출 #230725

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230725		nicolaalexandra	Potemkin cycle (CEOI15_indcyc)	C++14	30 / 100	1097 ms	10856 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 viz[DIM];

int verif (int nod, int tata){
    for (auto vecin : L[nod])
        if (vecin != tata && s.find(vecin) != s.end())
            return 0;
    return 1;
}
void dfs (int nod, int dest){
    if (ok)
        return;

    d.push_back(nod);
    s.insert(nod);
    viz[nod] = 1;
    if (nod == dest && d.size() >= 4){
        sol = d;
        ok = 1;
        return;
    }

    for (auto vecin : L[nod])
        if (!viz[vecin] && verif(vecin,nod))
            dfs (vecin,dest);

    /// 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);
        mch.push_back(make_pair(x,y));
    }

    for (auto it : mch){
        int x = it.first, y = it.second;
        /// sterg muchia x,y
        L[x].erase(y);
        L[y].erase(x);

        d.clear(), s.clear();
        memset (viz,0,sizeof viz);
        ok = 0;

        dfs (x,y);

        if (ok){
            for (auto it : sol)
                cout<<it<<" ";
            return 0;
        }

        L[x].insert(y);
        L[y].insert(x);
    }

    cout<<"no";

    return 0;
}

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