---

图专题2(PAT)：

1.第一次接触

第一次接触

 

2.最大集团

最大集团

 

3.拓扑顺序

拓扑顺序

 

4.旅行商问题

旅行商问题

 

5.顶点着色

顶点着色

 

6.公共自行车管理

公共自行车管理

 

7.加油站

加油站

 

8.微博转发

微博转发

 

AC代码:

1.第一次接触

// 注意输入输出格式,输入会有-0000这种格式,所以不能直接根据正负性判断男和女!输出注意%04d
# include <iostream>
# include <vector>
# include <math.h>
# include <algorithm>
# include <cstring>
# include <unordered_map>
using namespace std;
const int MM = 1.5e4 + 10;
const int N = 1e4 + 10;
int h[N],ne[MM * 2],e[MM * 2],idx = 0;
typedef pair<int,int> PII;
int gender[N]; // True为女生,false为男生
bool st[N];
int n,m;
int dfs_gender[4];
char in_a[10],in_b[10];
vector<int> ans;
vector<PII> val;
unordered_map<int,unordered_map<int,int> > M;

void add(int a,int b){
  e[idx] = b,ne[idx] = h[a],h[a] = idx ++;  
}

void dfs(int u,int v,int f){
  if (f == 2){
    if (M[u][v] == 1){ /...