Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：#
给出n个点，条边的无向图，无重边，无自环。现在要求把所有的无向边换成有向边，使得入度为0的点最少。问最少的入度为0的点是多少。
思路：#
对于每个联通快，如果有环，我们可以顺时针连接环上的点，以指向环的方向连接联通快上的其他点，这样就可以保证所有点的入度都不为0. 如果是树形结构，则不可避免得使得一个点的入度为0.
因此对于有环的联通块答案为0，没环的答案为1.
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月25日 星期三 20时57分54秒
4File Name :E.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23const int N = 1E5+7;
24vector <int>edge[N];
25bool vis[N];
26
27bool dfs( int u,int pre)
28{
29 vis[u] = true;
30 // cout<<"u:"<<u<<" pre:"<<pre<<endl;
31 int siz = edge[u].size();
32 for ( int i = 0 ; i < siz ; i++)
33 {
34 int v = edge[u][i];
35 if (v==pre) continue; //无向边
36 if (vis[v]||dfs(v,u)) return true;
37 }
38 return false;
39}
40int n,m;
41int main()
42{
43 #ifndef ONLINE_JUDGE
44 freopen("./in.txt","r",stdin);
45 #endif
46
47 ms(vis,false);
48 cin>>n>>m;
49 while (m--)
50 {
51 int x,y;
52 scanf("%d %d",&x,&y);
53 edge[x].PB(y);
54 edge[y].PB(x);
55 }
56
57 int ans = 0 ;
58 for ( int i = 1 ; i <= n ; i++)
59 if (!dfs(i,-1)) ans++;
60
61 cout<<ans<<endl;
62
63
64
65 #ifndef ONLINE_JUDGE
66 fclose(stdin);
67 #endif
68 return 0;
69}