Submission #1034717

#TimeUsernameProblemLanguageResultExecution timeMemory
1034717vjudge1Pipes (CEOI15_pipes)C++17
40 / 100
710 ms65536 KiB
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
 
const int maxn = 1e5 + 20;
 
struct dsu
{
	int p[maxn];
 
	dsu()
	{
		memset(p , -1 , sizeof p);
	}
 
	int root(int v)
	{
		return (p[v] < 0? v : p[v] = root(p[v]));
	}
 
	bool merge(int v , int u)
	{
		v = root(v) , u = root(u);
		if(v == u)
			return 0;
 
		if(-p[v] < -p[u])
			swap(v , u);
 
		p[v] += p[u];
		p[u] = v;
		return 1;
	}
};
 
dsu tree , tc;
 
int dp[maxn] , h[maxn];
 
bool visited[maxn];
 
vector<int> adj[maxn];
 
void dfs(int v , int p = -1)
{
	visited[v] = 1;
	dp[v] = h[v];
 
	bool seen = 0;
	for(auto u : adj[v])
	{
		if(!visited[u])
		{
			h[u] = h[v] + 1;
			dfs(u , v);
			dp[v] = min(dp[v] , dp[u]);
		}
		else if(h[u] < h[v] - 1 || seen)
			dp[v] = min(dp[v] , h[u]);
 
		seen |= (u == p);
	}
 
	if(p != -1 && dp[v] >= h[v])
		cout << v + 1 << " " << p + 1 << endl;
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int n , m;
	cin >> n >> m;
 
	for(int i = 0; i < m; i++)
	{
		int a , b;
		cin >> a >> b;
		a-- , b--;
 
		if(tree.merge(a , b) || tc.merge(a , b))
			adj[a].pb(b) , adj[b].pb(a);
	}
 
	for(int i = 0; i < n; i++)
		if(!visited[i])
			dfs(i);
}
 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...