Submission #95125

#	Time	Username	Problem	Language	Result	Execution time	Memory
95125		ekrem	Potemkin cycle (CEOI15_indcyc)	C++98	100 / 100	264 ms	5368 KiB

indcyc

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1005
#define M 100005
using namespace std;

typedef pair < int , int > ii;

int n, m, r, grp, h[N], vis[N], u[N][N], uu[N], a[N][N], par[N];
vector < int > g[N];
queue < ii > q;

void dfs(int node){
	h[node] = grp;
	if(uu[node])
		return;
	for(int i = 0; i < g[node].size(); i++)
		if(!h[g[node][i]])
			dfs(g[node][i]);
}

void sp(int uuu, int v){
	// cout << "AMK" << uuu << " " << v << endl;

	vis[r] = 1;
	for(int i = 0; i < g[r].size(); i++)
		vis[g[r][i]] = 1;
	vis[v] = 0;

	q.push(mp(uuu, r));
	while(!q.empty()){
		int node = q.front().st;
		int pr = q.front().nd;
		q.pop();
		// cout << pr << " " << node << endl;

		par[node] = pr;

		if(node == v){
			while(node != 0){
				printf("%d ", node);
				node = par[node];
			}
			exit(0);
		}

		for(int i = 0; i < g[node].size(); i++)
			if(!vis[g[node][i]]){
				vis[g[node][i]] = 1;
				q.push(mp(g[node][i], node));
			}
	}
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d",&n ,&m);
	for(int i = 1; i <= m; i++){
		int u, v;
		scanf("%d %d",&u ,&v);
		a[u][v] = a[v][u] = 1;
		g[u].pb(v);
		g[v].pb(u);
	}

	for(r = 1; r <= n; r++){

		memset(h, 0, sizeof h);
		memset(uu, 0, sizeof uu);

		int sz = g[r].size();
		uu[r] = 1;
		for(int i = 0; i < sz; i++)
			uu[g[r][i]] = 1;


		// for(int i = 0; i < sz; i++)
		// 	for(int j = i + 1; j < sz; j++)
		// 		u[g[r][i]][g[r][j]] = u[g[r][j]][g[r][i]] = r;

		grp = 1;
		for(int i = 1; i <= n; i++)
			if(!h[i]){
				dfs(i);
				grp++;
			}

		// for(int i = 1; i <= n; i++)
		// 	cout << i << " " << h[i] << endl;

		for(int i = 0; i < sz; i++)
			for(int j = i + 1; j < sz; j++)
				if(!a[g[r][i]][g[r][j]] and h[g[r][i]] == h[g[r][j]])
					sp(g[r][i], g[r][j]);

	}
	puts("no");
	return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'void dfs(int)':
indcyc.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
indcyc.cpp: In function 'void sp(int, int)':
indcyc.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[r].size(); i++)
                 ~~^~~~~~~~~~~~~
indcyc.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < g[node].size(); i++)
                  ~~^~~~~~~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n ,&m);
  ~~~~~^~~~~~~~~~~~~~~~
indcyc.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u ,&v);
   ~~~~~^~~~~~~~~~~~~~~~

• 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