# Poj Solution 3177

```http://poj.org/problem?id=3177

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
static int a,cnt=1;
static int[] rank,un;
static boolean[][] map;
public static void main(String[] args) throws NumberFormatException, IOException
{
a=Integer.parseInt(ss[0]);
map=new boolean[a+1][a+1];
rank=new int[a+1];
un=new int[a+1];
for(int i=1;i<=a;i++)
un[i]=i;
int b=Integer.parseInt(ss[1]);
for(int i=0;i< b;i++)
{
int x=Integer.parseInt(ss[0]);
int y=Integer.parseInt(ss[1]);
map[x][y]=map[y][x]=true;
}
dsf(1,1,rank,un);
int cnt=0;
for(int i=1;i<=a;i++)
rank[i]=0;
for(int i=1;i<=a;i++)
{
int yy=root(i,un);
for(int j=1;j<=a;j++)
{
if(!map[i][j]) continue;
int ww=root(j,un);
if(ww!=yy)
{
rank[yy]++;
if(rank[yy]>1) break;
}
}
}
for(int i=1;i<=a;i++)
{
if(rank[i]==1)cnt++;
}
System.out.println((cnt+1)/2);
}

static void dsf(int n,int pre,int[] rank,int[] un)
{
if(rank[n]!=0)
{
for(int i=1;i<=a;i++)
if(rank[i]>rank[n]) union(i,n,un);
}
else
{
rank[n]=cnt++;
for(int i=1;i<=a;i++)
{
if(map[i][n]&&i!=pre&&root(i,un)!=root(n,un))
dsf(i,n,rank,un);
}
rank[n]=0;
}
}

static void union(int a,int b,int[] un)
{
int x1=root(a,un);
int y1=root(b,un);
if(x1>y1)un[x1]=y1;
else un[y1]=x1;
}

static int root(int a,int[] un)
{
int b=a;
while(b!=un[b])
b=un[b];
return un[a]=b;
}
}

```
This entry was posted in poj. Bookmark the permalink.