답안 #115845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
115845	2019-06-09T10:13:59 Z	rajarshi_basu	Potemkin cycle (CEOI15_indcyc)	C++14	컴파일 오류	0 ms	0 KB

indcyc

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>

using namespace std;

const int INF = 1e9+10;
const int MAXN = 1000+10;

int n,m;
bool mat[MAXN][MAXN];
bool vis[MAXN][MAXN];

stack<ii> cyc;
set<int> allnode;
bool done = 0;

inline bool isok(int a,int b,int c){
	return (!(mat[a][b] and mat[b][c] and mat[a][c])) and mat[b][c];
}

void dfs1(ii node){
	if(done)return;
	cyc.push(node);
	//cout << node.ff << " " << node.ss << endl;
	if(vis[node.ff][node.ss]){
		// we got our cycle

		allnode.insert(node.ff);
		allnode.insert(node.ss);
		cyc.pop();
		while(cyc.size()>0){
			ii x = cyc.top();cyc.pop();
			allnode.insert(x.ff);
			allnode.insert(x.ss);	
			if(x == node)break;
		}	
		done = 1;
		return;
	}

	vis[node.ff][node.ss] = 1;
	FOR(nxt,n){
		if(nxt == node.ff)continue;
		if(isok(node.ff,node.ss,nxt)){
			// this is a valid edge;
			dfs1({node.ss,nxt});
			if(done)return;
		}

	}

	if(cyc.size()>0)cyc.pop();
}

bool impNode[MAXN];
bool vis2[MAXN];
stack<int> st;
vector<int> cc;
void dfs2(int node,int p = -1){
	if(done)return;
	st.push(node);

	if(vis2[node]){
		st.pop();
		while(1){
			int x = st.top();st.pop();
			cc.pb(x);
			if(x == node)break;
		}
		done = 1;
		return;
	}
	vis2[node] = 1;
	FOR(i,n){
		if(node == i)continue;
		if(!mat[i][node])continue;
		if(!impNode[i])continue;
		if(p == i)continue;
		
		dfs2(i,node);
		
	}

	if(st.size()>0)st.pop();
}

int main(){
	cin >> n >> m;
	FOR(i,m){
		int a,b;
		cin >> a >> b;
		a--;b--;
		mat[a][b] = mat[b][a] = 1;
	}
	// input done
	FOR(i,n){
		dfs1({i,i});
	}
	if(!done){
		cout << "no1" << endl;
		return 0;
	}
	int x;
	for(auto e:allnode){
		impNode[e] = 1;
		x = e;
	}
	for(auto e:allnode){
		//cout << e << endl;
	}
	done = 0;
	dfs2(x);
	if(cc.empty()){
		cout << "no" << endl;
	}else{
		for(auto e:cc){
			cout << e+1 << " ";
		}
		cout << endl;
	}
	return 0;
}#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>

using namespace std;

const int INF = 1e9+10;
const int MAXN = 1000+10;

int n,m;
bool mat[MAXN][MAXN];
bool vis[MAXN][MAXN];

stack<ii> cyc;
set<int> allnode;
bool done = 0;

inline bool isok(int a,int b,int c){
	return (!(mat[a][b] and mat[b][c] and mat[a][c])) and mat[b][c];
}

void dfs1(ii node){
	if(done)return;
	cyc.push(node);
	//cout << node.ff << " " << node.ss << endl;
	if(vis[node.ff][node.ss]){
		// we got our cycle

		allnode.insert(node.ff);
		allnode.insert(node.ss);
		cyc.pop();
		while(cyc.size()>0){
			ii x = cyc.top();cyc.pop();
			allnode.insert(x.ff);
			allnode.insert(x.ss);	
			if(x == node)break;
		}	
		done = 1;
		return;
	}

	vis[node.ff][node.ss] = 1;
	FOR(nxt,n){
		if(nxt == node.ff)continue;
		if(isok(node.ff,node.ss,nxt)){
			// this is a valid edge;
			dfs1({node.ss,nxt});
			if(done)return;
		}

	}

	if(cyc.size()>0)cyc.pop();
}

bool impNode[MAXN];
bool vis2[MAXN];
stack<int> st;
vector<int> cc;
void dfs2(int node,int p = -1){
	if(done)return;
	st.push(node);

	if(vis2[node]){
		st.pop();
		while(1){
			int x = st.top();st.pop();
			cc.pb(x);
			if(x == node)break;
		}
		done = 1;
		return;
	}
	vis2[node] = 1;
	FOR(i,n){
		if(node == i)continue;
		if(!mat[i][node])continue;
		if(!impNode[i])continue;
		if(p == i)continue;
		
		dfs2(i,node);
		
	}

	if(st.size()>0)st.pop();
}

int main(){
	cin >> n >> m;
	FOR(i,m){
		int a,b;
		cin >> a >> b;
		a--;b--;
		mat[a][b] = mat[b][a] = 1;
	}
	// input done
	FOR(i,n){
		dfs1({i,i});
	}
	if(!done){
		cout << "no1" << endl;
		return 0;
	}
	int x;
	for(auto e:allnode){
		impNode[e] = 1;
		x = e;
	}
	for(auto e:allnode){
		//cout << e << endl;
	}
	done = 0;
	dfs2(x);
	if(cc.empty()){
		cout << "no" << endl;
	}else{
		for(auto e:cc){
			cout << e+1 << " ";
		}
		cout << endl;
	}
	return 0;
}
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>

using namespace std;

const int INF = 1e9+10;
const int MAXN = 1000+10;

int n,m;
bool mat[MAXN][MAXN];
bool vis[MAXN][MAXN];

stack<ii> cyc;
set<int> allnode;
bool done = 0;

inline bool isok(int a,int b,int c){
	return (!(mat[a][b] and mat[b][c] and mat[a][c])) and mat[b][c];
}

void dfs1(ii node){
	if(done)return;
	cyc.push(node);
	//cout << node.ff << " " << node.ss << endl;
	if(vis[node.ff][node.ss]){
		// we got our cycle

		allnode.insert(node.ff);
		allnode.insert(node.ss);
		cyc.pop();
		while(cyc.size()>0){
			ii x = cyc.top();cyc.pop();
			allnode.insert(x.ff);
			allnode.insert(x.ss);	
			if(x == node)break;
		}	
		done = 1;
		return;
	}

	vis[node.ff][node.ss] = 1;
	FOR(nxt,n){
		if(nxt == node.ff)continue;
		if(isok(node.ff,node.ss,nxt)){
			// this is a valid edge;
			dfs1({node.ss,nxt});
			if(done)return;
		}

	}

	if(cyc.size()>0)cyc.pop();
}

bool impNode[MAXN];
bool vis2[MAXN];
stack<int> st;
vector<int> cc;
void dfs2(int node,int p = -1){
	if(done)return;
	st.push(node);

	if(vis2[node]){
		st.pop();
		while(1){
			int x = st.top();st.pop();
			cc.pb(x);
			if(x == node)break;
		}
		done = 1;
		return;
	}
	vis2[node] = 1;
	FOR(i,n){
		if(node == i)continue;
		if(!mat[i][node])continue;
		if(!impNode[i])continue;
		if(p == i)continue;
		
		dfs2(i,node);
		
	}

	if(st.size()>0)st.pop();
}

int main(){
	cin >> n >> m;
	FOR(i,m){
		int a,b;
		cin >> a >> b;
		a--;b--;
		mat[a][b] = mat[b][a] = 1;
	}
	// input done
	FOR(i,n){
		dfs1({i,i});
	}
	if(!done){
		cout << "no" << endl;
		return 0;
	}
	int x;
	for(auto e:allnode){
		impNode[e] = 1;
		x = e;
	}
	for(auto e:allnode){
		//cout << e << endl;
	}
	done = 0;
	dfs2(x);
	if(cc.empty()){
		cout << "no" << endl;
	}else{
		for(auto e:cc){
			cout << e+1 << " ";
		}
		cout << endl;
	}
	return 0;
}

Compilation message

indcyc.cpp:150:2: error: stray '#' in program
 }#include <iostream>
  ^
indcyc.cpp:161:19: warning: extra tokens at end of #include directive
 #include <fstream>#include <iostream>
                   ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:136:11: warning: unused variable 'e' [-Wunused-variable]
  for(auto e:allnode){
           ^
indcyc.cpp: At global scope:
indcyc.cpp:150:3: error: 'include' does not name a type
 }#include <iostream>
   ^~~~~~~
indcyc.cpp:194:11: error: redefinition of 'const int INF'
 const int INF = 1e9+10;
           ^~~
indcyc.cpp:34:11: note: 'const int INF' previously defined here
 const int INF = 1e9+10;
           ^~~
indcyc.cpp:195:11: error: redefinition of 'const int MAXN'
 const int MAXN = 1000+10;
           ^~~~
indcyc.cpp:35:11: note: 'const int MAXN' previously defined here
 const int MAXN = 1000+10;
           ^~~~
indcyc.cpp:197:5: error: redefinition of 'int n'
 int n,m;
     ^
indcyc.cpp:37:5: note: 'int n' previously declared here
 int n,m;
     ^
indcyc.cpp:197:7: error: redefinition of 'int m'
 int n,m;
       ^
indcyc.cpp:37:7: note: 'int m' previously declared here
 int n,m;
       ^
indcyc.cpp:198:20: error: redefinition of 'bool mat [1010][1010]'
 bool mat[MAXN][MAXN];
                    ^
indcyc.cpp:38:6: note: 'bool mat [1010][1010]' previously declared here
 bool mat[MAXN][MAXN];
      ^~~
indcyc.cpp:199:20: error: redefinition of 'bool vis [1010][1010]'
 bool vis[MAXN][MAXN];
                    ^
indcyc.cpp:39:6: note: 'bool vis [1010][1010]' previously declared here
 bool vis[MAXN][MAXN];
      ^~~
indcyc.cpp:201:11: error: redefinition of 'std::stack<std::pair<int, int> > cyc'
 stack<ii> cyc;
           ^~~
indcyc.cpp:41:11: note: 'std::stack<std::pair<int, int> > cyc' previously declared here
 stack<ii> cyc;
           ^~~
indcyc.cpp:202:10: error: redefinition of 'std::set<int> allnode'
 set<int> allnode;
          ^~~~~~~
indcyc.cpp:42:10: note: 'std::set<int> allnode' previously declared here
 set<int> allnode;
          ^~~~~~~
indcyc.cpp:203:6: error: redefinition of 'bool done'
 bool done = 0;
      ^~~~
indcyc.cpp:43:6: note: 'bool done' previously defined here
 bool done = 0;
      ^~~~
indcyc.cpp: In function 'bool isok(int, int, int)':
indcyc.cpp:205:13: error: redefinition of 'bool isok(int, int, int)'
 inline bool isok(int a,int b,int c){
             ^~~~
indcyc.cpp:45:13: note: 'bool isok(int, int, int)' previously defined here
 inline bool isok(int a,int b,int c){
             ^~~~
indcyc.cpp: In function 'void dfs1(std::pair<int, int>)':
indcyc.cpp:209:6: error: redefinition of 'void dfs1(std::pair<int, int>)'
 void dfs1(ii node){
      ^~~~
indcyc.cpp:49:6: note: 'void dfs1(std::pair<int, int>)' previously defined here
 void dfs1(ii node){
      ^~~~
indcyc.cpp: At global scope:
indcyc.cpp:243:18: error: redefinition of 'bool impNode [1010]'
 bool impNode[MAXN];
                  ^
indcyc.cpp:83:6: note: 'bool impNode [1010]' previously declared here
 bool impNode[MAXN];
      ^~~~~~~
indcyc.cpp:244:15: error: redefinition of 'bool vis2 [1010]'
 bool vis2[MAXN];
               ^
indcyc.cpp:84:6: note: 'bool vis2 [1010]' previously declared here
 bool vis2[MAXN];
      ^~~~
indcyc.cpp:245:12: error: redefinition of 'std::stack<int> st'
 stack<int> st;
            ^~
indcyc.cpp:85:12: note: 'std::stack<int> st' previously declared here
 stack<int> st;
            ^~
indcyc.cpp:246:13: error: redefinition of 'std::vector<int> cc'
 vector<int> cc;
             ^~
indcyc.cpp:86:13: note: 'std::vector<int> cc' previously declared here
 vector<int> cc;
             ^~
indcyc.cpp: In function 'void dfs2(int, int)':
indcyc.cpp:247:6: error: redefinition of 'void dfs2(int, int)'
 void dfs2(int node,int p = -1){
      ^~~~
indcyc.cpp:87:6: note: 'void dfs2(int, int)' previously defined here
 void dfs2(int node,int p = -1){
      ^~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:275:5: error: redefinition of 'int main()'
 int main(){
     ^~~~
indcyc.cpp:115:5: note: 'int main()' previously defined here
 int main(){
     ^~~~
indcyc.cpp:296:11: warning: unused variable 'e' [-Wunused-variable]
  for(auto e:allnode){
           ^
indcyc.cpp: At global scope:
indcyc.cpp:332:11: error: redefinition of 'const int INF'
 const int INF = 1e9+10;
           ^~~
indcyc.cpp:34:11: note: 'const int INF' previously defined here
 const int INF = 1e9+10;
           ^~~
indcyc.cpp:333:11: error: redefinition of 'const int MAXN'
 const int MAXN = 1000+10;
           ^~~~
indcyc.cpp:35:11: note: 'const int MAXN' previously defined here
 const int MAXN = 1000+10;
           ^~~~
indcyc.cpp:335:5: error: redefinition of 'int n'
 int n,m;
     ^
indcyc.cpp:37:5: note: 'int n' previously declared here
 int n,m;
     ^
indcyc.cpp:335:7: error: redefinition of 'int m'
 int n,m;
       ^
indcyc.cpp:37:7: note: 'int m' previously declared here
 int n,m;
       ^
indcyc.cpp:336:20: error: redefinition of 'bool mat [1010][1010]'
 bool mat[MAXN][MAXN];
                    ^
indcyc.cpp:38:6: note: 'bool mat [1010][1010]' previously declared here
 bool mat[MAXN][MAXN];
      ^~~
indcyc.cpp:337:20: error: redefinition of 'bool vis [1010][1010]'
 bool vis[MAXN][MAXN];
                    ^
indcyc.cpp:39:6: note: 'bool vis [1010][1010]' previously declared here
 bool vis[MAXN][MAXN];
      ^~~
indcyc.cpp:339:11: error: redefinition of 'std::stack<std::pair<int, int> > cyc'
 stack<ii> cyc;
           ^~~
indcyc.cpp:41:11: note: 'std::stack<std::pair<int, int> > cyc' previously declared here
 stack<ii> cyc;
           ^~~
indcyc.cpp:340:10: error: redefinition of 'std::set<int> allnode'
 set<int> allnode;
          ^~~~~~~
indcyc.cpp:42:10: note: 'std::set<int> allnode' previously declared here
 set<int> allnode;
          ^~~~~~~
indcyc.cpp:341:6: error: redefinition of 'bool done'
 bool done = 0;
      ^~~~
indcyc.cpp:43:6: note: 'bool done' previously defined here
 bool done = 0;
      ^~~~
indcyc.cpp: In function 'bool isok(int, int, int)':
indcyc.cpp:343:13: error: redefinition of 'bool isok(int, int, int)'
 inline bool isok(int a,int b,int c){
             ^~~~
indcyc.cpp:45:13: note: 'bool isok(int, int, int)' previously defined here
 inline bool isok(int a,int b,int c){
             ^~~~
indcyc.cpp: In function 'void dfs1(std::pair<int, int>)':
indcyc.cpp:347:6: error: redefinition of 'void dfs1(std::pair<int, int>)'
 void dfs1(ii node){
      ^~~~
indcyc.cpp:49:6: note: 'void dfs1(std::pair<int, int>)' previously defined here
 void dfs1(ii node){
      ^~~~
indcyc.cpp: At global scope:
indcyc.cpp:381:18: error: redefinition of 'bool impNode [1010]'
 bool impNode[MAXN];
                  ^
indcyc.cpp:83:6: note: 'bool impNode [1010]' previously declared here
 bool impNode[MAXN];
      ^~~~~~~
indcyc.cpp:382:15: error: redefinition of 'bool vis2 [1010]'
 bool vis2[MAXN];
               ^
indcyc.cpp:84:6: note: 'bool vis2 [1010]' previously declared here
 bool vis2[MAXN];
      ^~~~
indcyc.cpp:383:12: error: redefinition of 'std::stack<int> st'
 stack<int> st;
            ^~
indcyc.cpp:85:12: note: 'std::stack<int> st' previously declared here
 stack<int> st;
            ^~
indcyc.cpp:384:13: error: redefinition of 'std::vector<int> cc'
 vector<int> cc;
             ^~
indcyc.cpp:86:13: note: 'std::vector<int> cc' previously declared here
 vector<int> cc;
             ^~
indcyc.cpp: In function 'void dfs2(int, int)':
indcyc.cpp:385:6: error: redefinition of 'void dfs2(int, int)'
 void dfs2(int node,int p = -1){
      ^~~~
indcyc.cpp:87:6: note: 'void dfs2(int, int)' previously defined here
 void dfs2(int node,int p = -1){
      ^~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:413:5: error: redefinition of 'int main()'
 int main(){
     ^~~~
indcyc.cpp:115:5: note: 'int main()' previously defined here
 int main(){
     ^~~~
indcyc.cpp:434:11: warning: unused variable 'e' [-Wunused-variable]
  for(auto e:allnode){
           ^