Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <stdio.h>
- using namespace std;
- int T;
- int n,m;
- bool bri[100100];
- vector<int> adj[100100];
- vector<int> ind[100100];
- vector<int> adj2[100100];
- int aa,bb;
- int r,c;
- int ra[100100],lw[100100];
- int co[100100];
- bool vis[100100];
- int cnt,sol;
- int dp[100100];
- void bridge(int nd,int p){
- ra[nd]=r;
- lw[nd]=r;
- r++;
- for(int i=0;i<adj[nd].size();i++){
- int ch=adj[nd][i];
- int id=ind[nd][i];
- if(ch==p)continue;
- if(ra[ch]==0){
- bridge(ch,nd);
- if(lw[ch]==ra[ch]){
- bri[id]=true;
- }
- lw[nd]=min(lw[nd],lw[ch]);
- } else {
- lw[nd]=min(lw[nd],ra[ch]);
- }
- }
- }
- void comp(int nd){
- vis[nd]=true;
- co[nd]=c;
- for(int i=0;i<adj[nd].size();i++){
- int ch=adj[nd][i];
- int id=ind[nd][i];
- if(bri[id])continue;
- if(vis[ch])continue;
- comp(ch);
- }
- }
- void diameter(int nd,int p){
- dp[nd]=0;
- int mx=-1,mx2=-1;
- for(int i=0;i<adj2[nd].size();i++){
- int ch=adj2[nd][i];
- if(ch==p)continue;
- diameter(ch,nd);
- dp[nd]=max(dp[nd],dp[ch]+1);
- if(dp[ch]>mx2){
- mx2=dp[ch];
- }
- if(mx2>mx){
- swap(mx2,mx);
- }
- }
- sol=max(sol,mx2+mx+2);
- }
- int main(){
- scanf("%d",&T);
- while(T--){
- scanf("%d %d",&n,&m);
- cnt=0;
- sol=0;
- r=1;
- c=1;
- for(int i=1;i<=n;i++){
- adj[i].clear();
- adj2[i].clear();
- ind[i].clear();
- ra[i]=0;
- lw[i]=0;
- co[i]=0;
- dp[i]=0;
- vis[i]=false;
- }
- for(int i=1;i<=m;i++){
- bri[i]=false;
- }
- for(int i=1;i<=m;i++){
- scanf("%d %d",&aa,&bb);
- adj[aa].push_back(bb);
- adj[bb].push_back(aa);
- ind[aa].push_back(i);
- ind[bb].push_back(i);
- }
- bridge(1,1);
- for(int i=1;i<=n;i++){
- if(!vis[i]){
- comp(i);
- c++;
- }
- }
- c--;
- for(int i=1;i<=n;i++){
- for(int j=0;j<adj[i].size();j++){
- int ch=adj[i][j];
- int id=ind[i][j];
- if(bri[id]){
- cnt++;
- adj2[ co[i] ].push_back( co[ch] );
- }
- }
- }
- cnt/=2;
- diameter(1,1);
- printf("%d\n",cnt-sol);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement