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>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll h[maxN];
ll lab[maxN];
vector<ll>vec[maxN],g[maxN];
ll findset(ll x)
{
return lab[x]<0?x:lab[x]=findset(lab[x]);
}
void unite(ll u,ll v)
{
u=findset(u);
v=findset(v);
if(u==v) return;
if(lab[u]>lab[v]) swap(u,v);
lab[u]+=lab[v];
lab[v]=u;
for(auto zz:vec[v]) vec[u].pb(zz);
vec[v].clear();
}
void dfs(ll u,ll p)
{
for(int v:g[u])
{
if(v!=p)
{
h[v]=h[u]+1;
dfs(v,u);
}
}
}
ll ans=0;
ll m;
ll n;
void solve()
{
cin >> n >> m;
for(int i=1;i<=n;i++) lab[i]=-1,vec[i].pb(i);
for(int i=1;i<=m;i++)
{
ll u,v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
unite(u,v);
}
for(int i=1;i<=n;i++)
{
if(findset(i)==i)
{
dfs(i,0);
ll mx=-1,id=-1;
h[i]=0;
for(auto zz:vec[i])
{
if(h[zz]>mx)
{
mx=h[zz];
id=zz;
}
}
h[id]=0;
dfs(id,0);
mx=-1;
for(auto zz:vec[i])
{
mx=max(mx,h[zz]);
}
ans+=mx+1;
}
}
cout << ans;
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
# | 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... |