题意:给你一个无向图,如今要求你把边改成有向的。 使得入度为0的点最少,输出有多少个点入度为0
思路:脑补一波结论。假设有环的话显然没有点入度为0,其余则至少有一个点入度为0,然后就DFS一波就能够了
#include <cstdio> #include <queue> #include <cstring> #include <iostream> #include <cstdlib> #include <algorithm> #include <vector> #include <map> #include <string> #include <set> #include <ctime> #include <cmath> #include <cctype> using namespace std; #define maxn 100000+1000 #define LL long long int cas=1,T; vector<int> e[maxn]; int vis[maxn]; int flag=0; void dfs(int u,int fa) { if (vis[u]) { flag=1; return; } vis[u]=1; for (int i=0;i<e[u].size();i++) { int v = e[u][i]; if (v==fa) continue; dfs(v,u); } } int main() { int n,m; scanf("%d%d",&n,&m); for (int i = 1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); } int ans = 0; for (int i = 1;i<=n;i++) { if (!vis[i]) {
flag = 0; dfs(i,-1); if (!flag) ans++; } } printf("%d\n",ans); //freopen("in","r",stdin); //scanf("%d",&T); //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC); return 0; }
原文:http://www.cnblogs.com/mthoutai/p/7261262.html