//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define F first
#define S second
//#pragma GCC optimize("Ofast")
const int maxn = 1e5 + 5, maxlog = 19;
int n, m, pr[maxn], x, y, par[maxn][maxlog], h[maxn], cnt[maxn], cnt2[maxn];
bitset<maxn * 60> bs;
vector<int> adj[maxn];
bool vis[maxn];
int getpar(int v)
{
if(pr[v] == 0)
return pr[v] = v;
return (v == pr[v] ? v : pr[v] = getpar(pr[v]));
}
bool un(int v, int u)
{
v = getpar(v);
u = getpar(u);
if(u != v)
{
pr[u] = v;
return 1;
}
return 0;
}
void dfs(int v = 1, int p = 0, int hi = 1)
{
vis[v] = 1;
par[v][0] = p;
h[v] = hi;
for(int i = 1; i < maxlog; i++)
par[v][i] = par[par[v][i - 1]][i - 1];
for(auto u : adj[v])
if(u != p)
dfs(u, v, hi + 1);
}
int lca(int v, int u)
{
if(h[v] < h[u])
swap(v, u);
for(int i = maxlog - 1; i >= 0; i--)
if(h[par[v][i]] >= h[u])
v = par[v][i];
for(int i = maxlog - 1; i >= 0; i--)
if(par[v][i] != par[u][i])
u = par[v][i], u = par[u][i];
return (v == u ? v : par[v][0]);
}
void dfs2(int v = 1, int p = 0)
{
cnt2[v] = cnt[v];
for(auto u : adj[v])
if(u != p)
dfs2(u, v), cnt2[v] += cnt2[u];
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++)
{
cin >> x >> y;
if(un(x, y))
{
adj[x].pb(y);
adj[y].pb(x);
bs[i] = 1;
}
}
for(int i = 1; i <= n; i++)
if(!vis[i])
dfs(i);
cin.seekg(0, ios::beg);
cin >> n >> m;
for(int i = 0; i < m; i++)
{
cin >> x >> y;
if(bs[i] == 1)
continue;
//cout << x << " " << y << '\n';
cnt[x] ++;
cnt[y] ++;
cnt[lca(x, y)] -= 2;
}
//return 0;
memset(vis, 0, maxn);
for(int i = 1; i <= n; i++)
if(!vis[i])
dfs2(i);
vector<pair<int, int> > ans;
for(int i = 2; i <= n; i++)
if(cnt2[i] == 0&& par[i][0] != 0)
ans.pb({i, par[i][0]});
cout << ans.size() << '\n';
for(auto x : ans)
cout << x.F << " " << x.S << '\n';
}
/*
10 11
1 7
1 8
1 6
2 8
6 7
5 8
2 5
2 3
2 4
3 4
10 9
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2764 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
462 ms |
3340 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
629 ms |
3192 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3460 ms |
3956 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5046 ms |
5580 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5082 ms |
11316 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5089 ms |
12592 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5091 ms |
14948 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5090 ms |
14864 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5097 ms |
14128 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |