제출 #116689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
116689		fleimgruber	Pipes (CEOI15_pipes)	C++17	60 / 100	1543 ms	51028 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;

//bridge finding
int n,t,in[MAX_N];
vector<int> e[MAX_N];

int dfs(int i, int p = -1)
{
	in[i] = ++t;
	int lo = in[i];
	for (int g : e[i])
	{
		if (g == p)
		{
			p = -1;
			continue;
		}
		if (in[g])
			lo = min(lo,in[g]);
		else
		{
			int lg = dfs(g,i);
			if (lg > in[i])
				printf("%d %d\n",i,g);
			lo = min(lo,lg);
		}
	}
	return lo;
}

void bridges()
{
	for (int i=1; i<=n; i++)
		if (!in[i])
			dfs(i);
}
//-----

struct
{
	int p[MAX_N],s[MAX_N];

	void init(int n)
	{
		for (int i=1; i<=n; i++)
			p[i] = i, s[i] = 1;
	}

	int f(int i)
	{
		if (p[i] == i)
			return i;
		return p[i]=f(p[i]);
	}
	
	bool connect(int a, int b)
	{
		a = f(a), b = f(b);
		if (a == b)
			return false;
		if (s[a] > s[b])
			swap(a,b);
		p[a] = b;
		s[b] += s[a];
		return true;
	}
} d1,d2;

int main()
{
	int m,a,b;
	scanf("%d %d",&n,&m);
	d1.init(n), d2.init(n);
	int cnt = 0;
	while (m--)
	{
		scanf("%d %d",&a,&b);
		if (d1.connect(a,b) || d2.connect(a,b))
		{
			cnt++;
			assert(cnt < 2*n);
			e[a].push_back(b);
			e[b].push_back(a);
		}
	}
	bridges();
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

pipes.cpp: In function 'int main()':
pipes.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
pipes.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~~

• 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: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10