poj2186

maksyuki 发表于 oj 分类，标签:
22 1月 2016
0

Popular Cows

Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.

Input

* Line 1: Two space-separated integers, N and M

* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.

Output

* Line 1: A single integer that is the number of cows who are considered popular by every other cow.

Sample Input

3 3

1 2

2 1

2 3

Sample Output

1

Hint

Cow 3 is the only cow of high popularity.

Source

USACO 2003 Fall

 

题目类型：有向图重连通分量(Tarjan)+缩点

算法分析：由于仰慕关系可以传递，则若一个强连通分量Q中的某个点被外部点A所仰慕，则Q中所有点都会被A仰慕。同样，若Q中的某个点仰慕某个外部点B，则Q中所有点都会仰慕B。所以可以缩点，找新构成的图中出度为0的点(注意这个点是可能是缩点！！！)，若出度为0的点的个数不为1，则输出0。否则输出当前缩点中点的个数

 

poj2762

maksyuki 发表于 oj 分类，标签: ,
22 1月 2016
0

Going from u to v or from v to u?

In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?

Input

The first line contains a single integer T, the number of test cases. And followed T cases.

The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.

Output

The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.

Sample Input

1

3 3

1 2

2 3

3 1

Sample Output

Yes

Source

POJ Monthly--2006.02.26,zgl & twb

 

题目类型：有向图强连通分量(Tarjan) +缩点+拓扑排序判定

算法分析：这个题目要判断一个图是否是单连通的，由于图中同一个强连通分量中的点一定是单连通的，所以可以不用考虑同一个强连通分量中的所有点之间的连通情况继而将其缩成一个点。然后考察缩完点之后的图，易知这个图任意两点之间最多单向可达。由于处理后得到的图仍然是有向图，所以可以对图进行拓扑排序。对于得到的拓扑序列，相邻的节点要么是”非同层”顶点，要么是”同层”顶点(拓扑排序过程中某次入度为0的顶点之间互为”同层”顶点)。对于以上两种情况，只要满足拓扑序中所有相邻的顶点之间邻接，则由传递性可知，每个顶点之间都可达

 

poj3177

maksyuki 发表于 oj 分类，标签:
22 1月 2016
0

Redundant Paths

In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples. The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another.

Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way.

There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path.

Input

Line 1: Two space-separated integers: F and R

Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.

Output

Line 1: A single integer that is the number of new paths that must be built.

Sample Input

7 7

1 2

2 3

3 4

2 5

4 5

5 6

5 7

Sample Output

2

Hint

Explanation of the sample:

One visualization of the paths is:

1   2   3
+---+---+
|   |
|   |
6 +---+---+ 4
/ 5
/
/
7 +

Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions.

1   2   3
+---+---+
:   |   |
:   |   |
6 +---+---+ 4
/ 5  :
/     :
/      :
7 + - - - -

Check some of the routes:
1 – 2: 1 –> 2 and 1 –> 6 –> 5 –> 2
1 – 4: 1 –> 2 –> 3 –> 4 and 1 –> 6 –> 5 –> 4
3 – 7: 3 –> 4 –> 7 and 3 –> 2 –> 5 –> 7
Every pair of fields is, in fact, connected by two routes.

It's possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.

Source

USACO 2006 January Gold

 

题目类型：无向图求割边(Tarjan)+缩点

算法分析：这里虽然存在重边，但是可以不将重边加入到图中，然后使用low值将边重连通分量进行划分，若图中没有重边，则low值相同的顶点一定在一个边重连通分量中(因为有环)。所以此时可以双重循环枚举找邻接顶点，若两个顶点的low不同，则它们各自所在的“缩点”的度数自加1

 

poj3352

maksyuki 发表于 oj 分类，标签: ,
22 1月 2016
0

Road Construction

It's almost summer time, and that means that it's almost summer construction time! This year, the good people who are in charge of the roads on the tropical island paradise of Remote Island would like to repair and upgrade the various roads that lead between the various tourist attractions on the island.

The roads themselves are also rather interesting. Due to the strange customs of the island, the roads are arranged so that they never meet at intersections, but rather pass over or under each other using bridges and tunnels. In this way, each road runs between two specific tourist attractions, so that the tourists do not become irreparably lost.

Unfortunately, given the nature of the repairs and upgrades needed on each road, when the construction company works on a particular road, it is unusable in either direction. This could cause a problem if it becomes impossible to travel between two tourist attractions, even if the construction company works on only one road at any particular time.

So, the Road Department of Remote Island has decided to call upon your consulting services to help remedy this problem. It has been decided that new roads will have to be built between the various attractions in such a way that in the final configuration, if any one road is undergoing construction, it would still be possible to travel between any two tourist attractions using the remaining roads. Your task is to find the minimum number of new roads necessary.

Input

The first line of input will consist of positive integers n and r, separated by a space, where 3 ≤ n ≤ 1000 is the number of tourist attractions on the island, and 2 ≤ r ≤ 1000 is the number of roads. The tourist attractions are conveniently labelled from 1 to n. Each of the following r lines will consist of two integers, v and w, separated by a space, indicating that a road exists between the attractions labelled v and w. Note that you may travel in either direction down each road, and any pair of tourist attractions will have at most one road directly between them. Also, you are assured that in the current configuration, it is possible to travel between any two tourist attractions.

Output

One line, consisting of an integer, which gives the minimum number of roads that we need to add.

Sample Input

Sample Input 1

10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10

Sample Input 2

3 3

1 2

2 3

1 3

Sample Output

Output for Sample Input 1

2

Output for Sample Input 2

0

Source

CCC 2007

 

题目类型：无向图求割边(Tarjan)+缩点(并查集)

算法分析：首先可知在同一个重连通分量(边)中的点之间一定存在至少两条独立的路径，即可以不用考虑在同一个重连通分量中的点之间建路。这样的话可以将同一个连通分量缩成一个点，最后得到的图一定是一个树，且树中的边一定是割边(没有缩掉)。最后在两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先路径上所有的点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1) / 2次(leaf为树中叶子节点的个数)把所有点收缩到了一起。这里使用栈来记录每次找到的重连通分量(边)，使用并查集来缩点，注意这里任意两点之间没有重边！！！

算法分析：也可以直接使用POJ3177求解无向图(有重边)的方法来求解

链接：http://www.maksyuki.com/?p=2719