This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 1e5 + 20;
const int maxb = 20;
int st[maxn] , ft[maxn] , now = -1 , par[maxn][maxb] , p[maxn] , val[maxn];
vector<int> adj[maxn];
bitset<maxn * 100> is;
bool visited[maxn];
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;
}
bool is_par(int v , int u)
{
return st[v] <= st[u] && st[u] <= ft[v];
}
int lca(int v , int u)
{
for(int i = maxb - 1; i >= 0; i--)
if(!is_par(par[v][i] , u))
v = par[v][i];
if(is_par(v , u))
return v;
else
return par[v][0];
}
void dfs(int v , int p = -1)
{
if(p == -1)
for(int i = 0; i < maxb; i++)
par[v][i] = v;
visited[v] = 1;
st[v] = ++now;
for(auto u : adj[v])
if(u != p)
{
par[u][0] = v;
for(int i = 1; i < maxb; i++)
par[u][i] = par[par[u][i - 1]][i - 1];
dfs(u , v);
}
ft[v] = now;
}
void solve(int v , int p = -1)
{
visited[v] = 1;
for(auto u : adj[v])
if(u != p)
solve(u , v) , val[v] += val[u];
if(p != -1 && !val[v])
cout << v + 1 << " " << p + 1 << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(p , -1 , sizeof p);
int n , m;
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int a , b;
cin >> a >> b;
a-- , b--;
if(!merge(a , b))
is[i] = 1;
else
adj[a].pb(b) , adj[b].pb(a);
}
for(int i = 0; i < n; i++)
if(!visited[i])
dfs(i);
cin.seekg(0);
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int a , b;
cin >> a >> b;
a-- , b--;
if(is[i])
{
int c = lca(a , b);
val[a]++ , val[b]++ , val[c] -= 2;
}
}
memset(visited , 0 , sizeof visited);
for(int i = 0; i < n; i++)
if(!visited[i])
solve(i);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |