CodeForces 659E New Reform (DFS)
1511 ワード
http://codeforces.com/contest/659/problem/E
問題:n個の点の中でm条の無方向の辺が存在して、もしこのm条の辺で方向をプラスするならば、方向は唯一で、しかし任意であることができて、度を求めて0の点の個数は最大でいくらです
考え方:各点をループ検索し、ループが存在する場合、ループ内の点入度は0ではなく、ループ外の点がループ内の点から到達できれば、入度は0ではない
問題:n個の点の中でm条の無方向の辺が存在して、もしこのm条の辺で方向をプラスするならば、方向は唯一で、しかし任意であることができて、度を求めて0の点の個数は最大でいくらです
考え方:各点をループ検索し、ループが存在する場合、ループ内の点入度は0ではなく、ループ外の点がループ内の点から到達できれば、入度は0ではない
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
#define N 110000
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define MOD 1000000007
#define met(a, b) memset (a, b, sizeof(a))
const double EPS = 1e-8;
vector <vector <int> > G;
int n, m, vis[N], k;
void DFS (int u, int v)
{
if (vis[u])
{
k = 0;
return;
}
vis[u] = 1;
for (int i=0; i<G[u].size(); i++)
{
if (G[u][i] != v)
DFS (G[u][i], u);
}
}
int main ()
{
while (scanf ("%d %d", &n, &m) != EOF)
{
G.clear();
G.resize (n+1);
met (vis, 0);
while (m--)
{
int a, b;
scanf ("%d %d", &a, &b);
G[a].push_back (b);
G[b].push_back (a);
}
int ans = 0;
for (int i=1; i<=n; i++)
{
if (vis[i]) continue;
k = 1;
DFS (i, 0);
ans += k;
}
printf ("%d
", ans);
}
return 0;
}