NC50426. 原始生物
描述
输入描述
第一行是一个整数n，表示特征的总数。在接下来的n行里，每行都是一对由空格分隔的自然数l和r。数对(l,r)是原始生物的特征之一。输入文件中的特征不会有重复。
输出描述
唯一一行应该包含一个整数，等于包含了输入文件中所有特征的遗传密码的最小长度。
示例1
输入:
12 2 3 3 9 9 6 8 5 5 7 7 6 4 5 5 1 1 4 4 2 2 8 8 6
输出:
15
说明:
输入文件中的所有特征都包含在以下遗传密码中：Java(javac 1.8) 解法, 执行用时: 209ms, 内存消耗: 28072K, 提交时间: 2021-03-15 11:31:13
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
public class Main {
static class Task {
public int[] tn(int a){
int f[] = new int[11];
if(a==0) {
return new int[2];
}
int p = 1;
while(a>0){
int w = a%10;
f[p++] = w;
a/=10;
}
return Arrays.copyOf(f,p);
}
public int[] tt(String a){
int f[] = new int[2010];
int p = 1;
for(int i=a.length()-1;i>=0;--i) {
f[p++] = a.charAt(i)-'0';
}
return Arrays.copyOf(f, p);
}
static int rt = 0;
static int ch[][] ;
static int fa[];
static int id[];
static int mk[];
static int ct = 1;
static int cnt[];
static void insert(String s,int j,int num) {
int p = 0; // root
for (char c : s.toCharArray()) {
int d = c - 'a';
if (ch[p][d] == 0) {
ch[p][d] = ct++;
}
p = ch[p][d];
// mk[p]+= num;
}
mk[p] = 1;
// id[p] = 1 << j;
}
static int q[] ;
static int q1[] ;
static void build(){
int s = 0; int e = 0;
for(int i=0;i<26;++i) {
if(ch[0][i]>0) {
q[e++] = ch[0][i];
}
}
while(s<e){
int c = q[s++];
// if(id[fa[c]]>0){
// id[c] = id[fa[c]];
// }
mk[c] |= mk[fa[c]];
for(int j=0;j<26;++j){
if(ch[c][j]>0){
fa[ch[c][j]] = ch[fa[c]][j];
q[e++] = ch[c][j];
}else{
ch[c][j] = ch[fa[c]][j];
}
}
}
// for(int i=e-1;i>=0;--i){
// if(id[q[i]]!=-1){
// cnt[id[q[i]]] += mk[q[i]];
// }
// mk[fa[q[i]]] += mk[q[i]];
// }
}
static int search(String s){
int at = 0;
int cnt = 0;
for(char c:s.toCharArray()){
int to = c-'a';
to = ch[at][to];
int j = to;
while(j != 0) {
cnt += mk[to];
j = fa[j];
}
}
return cnt;
}
int p[][];double d[];int fat[];int sz[];
int sdp[][];
void get(int i,int j,List<Integer> li){
if(sdp[i][j]==0) return;
get(i,sdp[i][j],li);
li.add(sdp[i][j]);
get(sdp[i][j],j,li);
}
interface Func{
void add(int u,int v);
}
int root(int f){
return fat[f] = fat[f]!=f?root(fat[f]):f;
}
void combine(int x,int y){
int rt1 = root(x);
int rt2 = root(y);
if(rt1!=rt2){
fat[rt1] = rt2;
}
}
int ct1 = 0;
int to[];int ne[];
int h[];
void dfs(int rt,int pass){
if(id[rt]>0){
Func fc = (x,y)->{
to[ct1] = y;
ne[ct1] = h[x];
h[x] = ct1++;
};
fc.add(id[pass],id[rt]);
// fc.add(id[rt],id[pass]);
pass = rt;
}
for(int i=0;i<26;++i){
if(ch[rt][i]>0){
dfs(ch[rt][i], pass);
}
}
}
// edge number is small
boolean vis[];
public boolean spfa(int s, int n, double cut) {
d = new double[n];
Arrays.fill(d, -len);
int cnt[] = new int[n];
ArrayDeque<Integer> qu = new ArrayDeque<>();
qu.offer(s);
d[s] = 0;
double tot = 0;
boolean in[] = new boolean[n];
while (qu.size() > 0) {
int node = qu.poll();
//tot -= d[node];
in[node] = false;
vis[node] = true;
for (int i = h[node]; i != -1; i = ne[i]) {
int v = to[i];
double w = wt[i] - cut;
if (d[node] + w > d[v]) {
d[v] = d[node] + w;
if (++cnt[v] > n) {
return true;
}
if (!in[v]) {
tot += d[v];
if (!qu.isEmpty() && d[v] > d[qu.peekFirst()]) {
qu.offerFirst(v);
} else {
qu.offerLast(v);
}
// double x = tot / q.size();
// while (d[q.peekFirst()] < x) {
// q.offerLast(q.pollFirst());
// }
}
}
}
}
return false;
}
int wt[];
void add(int u,int v,int w){
to[ct] = v;
ne[ct] = h[u];
wt[ct] = w;
h[u] = ct++;
}
void g(int n,int m){
ct = 0;
h = new int[n];
Arrays.fill(h,-1);
to = new int[m];
ne = new int[m];
wt = new int[m];
}
double len = 0;
int b = 0;
boolean fob[];
int[] lu;
int tp;
void dfs11(int rt){
while(h[rt]!=-1){
if(st[h[rt]]){
h[rt] = ne[h[rt]];
continue;
}
st[h[rt]] = true;
int other = h[rt]^1;
st[other] = true;
int j = to[h[rt]];
int lj = wt[h[rt]];
h[rt] = ne[h[rt]];
dfs11(j);
lu[tp--] = lj;
}
}
boolean st[];
public void solve(int testNumber, InputReader in, PrintWriter out) {
int m = in.nextInt();
int n = 1000;
int rd[]= new int[n+1];
int cd[]= new int[n+1];
fat = new int[n+1];
for(int j=1;j<=n;++j){
fat[j] = j;
}
for(int i =0;i<m;++i) {
int u = in.nextInt();
int v = in.nextInt();
if(root(u)!=root(v)){
combine(u,v);
}
cd[u]++;rd[v]++;
}
int cnt[] = new int[n+1];
TreeSet<Integer> st = new TreeSet<>();
for(int j=1;j<=n;++j){
if(rd[j]+cd[j]==0) continue;
int mk = root(j);
cnt[mk] += Math.abs(cd[j] - rd[j]);
st.add(mk);
}
int r = 0;
if(st.size()==1){
int y = st.pollFirst();
if(cnt[y]>0){
r = cnt[y]/2-1;
}
}else{
for(int u:st){
if(cnt[u]>0) {
r += cnt[u]/2-1;
}else{
}
}
r += st.size()-1;
}
out.println(r+m+1);
}
// int t = in.nextInt();
// int n = in.nextInt();
// int m = in.nextInt();
//
// ct = 0;
// h = new int[n];Arrays.fill(h,-1);
// if(t==1) {
// to = new int[m * 2];
// ne = new int[m * 2];
//
// fob = new boolean[m * 2];
// }else{
// to = new int[m];
// ne = new int[m];
//
// }
//
//
// int rd[] = new int[n];
// int cd[] = new int[n];
// li = new int[m];
// tp = m-1;
//
// int rt= 0;
//
// for(int i=0;i<m;++i){
// int u = in.nextInt()-1;
// int v = in.nextInt()-1;
// add(u,v);
// if(t==1){
// add(v,u);
// }
// cd[u]++;
// rd[v]++;
// rt = u;
// }
//
// if(t==2){
//
// for(int i=0;i<n;++i){
// if(rd[i]!=cd[i]){
// out.println("NO");return;
// }
// }
// }else{
//
// for(int i=0;i<n;++i){
// if(((rd[i]+cd[i])%2)>0){
// out.println("NO");return;
// }
// }
//
// }
//
//
//
// dfs11(rt, t);
//
//
//
// if(tp!=-1){
// out.print("NO");
// return;
// }
//
// out.println("YES");
//
// for(int i=0;i<m;++i){
// out.print(li[i]+ " ");
// }
// int f1[][] = new int[q][3];
//
// for(int i=0;i<q;++i){
// for(int j=0;j<3;++j){
// f1[i][j] = in.nextInt();
// }
// }
//
//
// int h[] = new int[n+1];
//
// Arrays.fill(h,-1);
//
//
// int ne[] = new int[p*2+q];
// int to[] = new int[p*2+q];
// int wt[] = new int[p*2+q];
// ct = 0;
// Func fk = (int x,int y,int z) -> {
// to[ct] = y;
// ne[ct] = h[x];
// wt[ct] = z;
// h[x] = ct++;
// };
//
// for(int i=0;i<p;++i){
// int u = f[i][0];
// int v = f[i][1];
//
//
//
//
// fk.add(u,v,f[i][2]);
// fk.add(v,u,f[i][2]);
// }
//
// for(int i=0;i<q;++i){
// int u = f1[i][0];
// int v = f1[i][1];
//
//
//
//
// fk.add(u,v,f1[i][2]);
// }
// int dp[] = new int[n+1];
// Arrays.fill(dp,100000000);
// dp[s] = 0;
//
//
// PriorityQueue<int[]> qu = new PriorityQueue<>(Comparator.comparingInt((x)->x[0]));
// qu.add(new int[]{0,s});
// while(qu.size()>0){
// int cc[] = qu.poll();
// int cur = cc[1];
// if(cc[0]!=dp[cur]) continue;
// for(int j = h[cur];j!=-1;j=ne[j]){
// int v = to[j];
// if(dp[v] > dp[cur] + wt[j]){
// dp[v] = dp[cur] + wt[j];
// qu.offer(new int[]{dp[v],v});
// }
// }
// }
//
// for(int j=1;j<=n;++j){
// if(dp[j]==100000000){
// out.println("NO PATH");
// }else{
// out.println(dp[j]);
// }
// }
// for(int t=0;t<5;++t) {
// int at = fi[t];
// dp[at][t] = 0;
// PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt((x) -> x[0]));
// q.offer(new int[]{0, at});
// while (q.size() > 0) {
// int cur[] = q.poll();
// if (cur[0] != dp[cur[1]][t]) continue;
// int i = cur[1];
// for (int j = h[i]; j != -1; j = ne[j]) {
// int v = to[j];
// if (dp[i][t] + wt[j] < dp[v][t]) {
// dp[v][t] = dp[i][t] + wt[j];
// q.offer(new int[]{dp[v][t], v});
// }
// }
// }
// }
// int cl[] = new int[]{0,1,2,3,4};
// int rs = Integer.MAX_VALUE;
// do{
// int s= dp[1][cl[0]];
// for(int j=0;j<4;++j){
// int nxt = fi[cl[j+1]];
// s += dp[nxt][cl[j]];
// }
// rs = Math.min(rs,s);
//
//
// }while(next_perm(cl));
//
// out.print(rs);
boolean next_perm(int[] a){
int len = a.length;
for(int i=len-2,j = 0;i>=0;--i){
if(a[i]<a[i+1]){
j = len-1;
for(;a[j]<=a[i];--j);
int p = a[j];
a[j] = a[i];
a[i] = p;
j = i+1;
for(int ed = len-1;j<ed;--ed) {
p = a[ed];
a[ed] = a[j];
a[j++] = p;
}
return true;
}
}
return false;
}
static long mul(long a, long b, long p) {
long res = 0, base = a;
while (b > 0) {
if ((b & 1L) > 0)
res = (res + base) % p;
base = (base + base) % p;
b >>= 1;
}
return res;
}
static long mod_pow(long k, long n, long p) {
long res = 1L;
long temp = k % p;
while (n != 0L) {
if ((n & 1L) == 1L) {
res = mul(res, temp, p);
}
temp = mul(temp, temp, p);
n = n >> 1L;
}
return res % p;
}
public static double roundD(double result, int scale) {
BigDecimal bg = new BigDecimal(result).setScale(scale, RoundingMode.UP);
return bg.doubleValue();
}
}
private static void solve() {
InputStream inputStream = System.in;
// InputStream inputStream = null;
// try {
// inputStream = new FileInputStream(new File("D:\\chrome_download\\exp.out"));
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
OutputStream outputStream = System.out;
// OutputStream outputStream = null;
// File f = new File("D:\\chrome_download\\");
// try {
// f.createNewFile();
// } catch (IOException e) {
// e.printStackTrace();
// }
// try {
// outputStream = new FileOutputStream(f);
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task task = new Task();
task.solve(1, in, out);
out.close();
}
public static void main(String[] args) {
new Thread(null, () -> solve(), "1", (1 << 30)).start();
// solve();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String nextLine() {
String line = null;
try {
line = reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return line;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public char nextChar() {
return next().charAt(0);
}
public int[] nextArray(int n) {
int res[] = new int[n];
for (int i = 0; i < n; ++i) {
res[i] = nextInt();
}
return res;
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}
C++14(g++5.4) 解法, 执行用时: 39ms, 内存消耗: 488K, 提交时间: 2020-02-18 11:51:17
#include <bits/stdc++.h>
using namespace std;
int p[1024];
int find(int x) {
return p[x] = p[x] == x? x : find(p[x]);
}
int main() {
for (int i = 0; i < 1024; i++) p[i] = i;
int n; cin >> n;
vector<int> deg(1024);
set<int> S;
int joinCnt = 0;
for (int i = 0; i < n; i++) {
int u, v; cin >> u >> v;
deg[u]++, deg[v]--;
S.insert(u), S.insert(v);
int pu = find(u), pv = find(v);
if (pu != pv) joinCnt++, p[pu] = pv;
}
vector<int> cnt(1024);
for (int i = 0; i < 1024; i++) {
if (deg[i] > 0) cnt[find(i)] += deg[i];
}
int tot = 0;
for (int i = 0; i < 1024; i++) if (S.count(i) && i == find(i)) {
tot += max(cnt[i], 1);
}
cout << tot + n << endl;
}
C++11(clang++ 3.9) 解法, 执行用时: 42ms, 内存消耗: 476K, 提交时间: 2020-05-30 10:40:47
#include<bits/stdc++.h>
using namespace std;
int p[1024];
int find(int x)
{
return p[x]=p[x]==x?x:find(p[x]);
}
int main()
{
for(int i=0;i<1024;i++)
p[i]=i;
int n;
cin>>n;
vector<int> deg(1024);
set<int> S;
int joinCnt=0;
for(int i=0;i<n;i++)
{
int u,v;
cin>>u>>v;
deg[u]++,deg[v]--;
S.insert(u),S.insert(v);
int pu=find(u),pv=find(v);
if(pu!=pv) joinCnt++,p[pu]=pv;
}
vector<int> cnt(1024);
for(int i=0;i<1024;i++)
{
if(deg[i]>0) cnt[find(i)]+=deg[i];
}
int tot=0;
for(int i=0;i<1024;i++)
if(S.count(i)&&i==find(i))
{
tot+=max(cnt[i],1);
}
cout<<tot+n<<endl;
}