Submission #70110

#	Time	Username	Problem	Language	Result	Execution time	Memory
70110		Bodo171	Potemkin cycle (CEOI15_indcyc)	C++14	100 / 100	255 ms	6440 KiB

indcyc

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=1005;
bool ad[nmax][nmax];
vector<int> v[nmax],cyc,l;
int lev[nmax],prec[nmax],viz[nmax],d[nmax],valid[nmax],q[nmax];
int i,n,m,u,p,x,nod,a,b,start;
void construieste(int A,int B)
{
    while(A!=B)
    {
        cyc.push_back(A);
        A=prec[A];
    }
    cyc.push_back(B);
    cyc.push_back(start);
}
void dfs(int x)
{
    viz[x]=1;if(ad[start][x])l.push_back(x);
    if(!ad[start][x])
      for(int i=0;i<v[x].size();i++)
        if(!viz[v[x][i]])
    {
        dfs(v[x][i]);
    }
}
void get_cyc(int A,int B)
{
    for(int i=1;i<=n;i++)
        valid[i]=1;
    valid[start]=0;
    for(int i=0;i<v[start].size();i++)
        valid[v[start][i]]=0;
    valid[A]=valid[B]=1;
    q[u=1]=B;d[B]=1;
    for(p=1;p<=u;p++)
    {
         x=q[p];
         for(int i=0;i<v[x].size();i++)
         {
             nod=v[x][i];
             if((!d[nod])&&valid[nod])
             {
                 d[nod]=d[x]+1;
                 q[++u]=nod;
                 prec[nod]=x;
             }
         }
    }
    construieste(A,B);
}
void solve()
{
    for(i=1;i<=n;i++)
        prec[i]=viz[i]=0;
    u=0;
    for(int i=1;i<=n;i++)
        if((!viz[i])&&(!ad[start][i]))
      {
          l.clear();
          dfs(i);
          for(int j=0;j<l.size();j++)
            for(int k=j+1;k<l.size();k++)
          {
              if(!ad[l[j]][l[k]])
              {
                  get_cyc(l[j],l[k]);
                  return;
              }
          }
      }
}
int main()
{
  //  freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b;
        ad[a][b]=ad[b][a]=1;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1;i<=n;i++)
        ad[i][i]=1;
    for(start=1;start<=n&&cyc.size()==0;start++)
    {
        solve();
    }
    if(!cyc.size())
    {
        cout<<"no";
    }
    else
    {
        for(i=0;i<cyc.size();i++)
            cout<<cyc[i]<<' ';
    }
    return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'void dfs(int)':
indcyc.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<v[x].size();i++)
                   ~^~~~~~~~~~~~
indcyc.cpp: In function 'void get_cyc(int, int)':
indcyc.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[start].size();i++)
                 ~^~~~~~~~~~~~~~~~
indcyc.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          for(int i=0;i<v[x].size();i++)
                      ~^~~~~~~~~~~~
indcyc.cpp: In function 'void solve()':
indcyc.cpp:66:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for(int j=0;j<l.size();j++)
                       ~^~~~~~~~~
indcyc.cpp:67:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=j+1;k<l.size();k++)
                           ~^~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:101:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<cyc.size();i++)
                 ~^~~~~~~~~~~

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