寒假训练 DIV1（1）dfs及其应用1

A - The Necklace

欧拉路经

题目大意

给你n个珠子，一个珠子分为两半有两种颜色，用1到50来表示50种不同的颜色。把这些珠子串起来，两个紧挨着的珠子要满足一个条件就是接触的那部分颜色要相同

解题思路

给出两个数字是一条边，然后找出任意一个欧拉回路。 
无向图欧拉回路的条件： 
 1. 要联通 
 2. 每个节点度必须是偶数

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n;
const int N=55;
int mp[N][N],in[N];
void euler(int now)
{
    for (int i=1;i<=50;i++)
        if (mp[now][i])
        {
            mp[now][i]--;
            mp[i][now]--;
            euler(i);
            printf("%d %d\n",i,now);
            //一定要逆序输出 
        }
}
int main()
{
    int T;
    scanf("%d",&T);
    for (int TT=1;TT<=T;TT++)
    {
        memset(mp,0,sizeof(mp));
        memset(in,0,sizeof(in));
        scanf("%d",&n);
        int s;
        for (int i=1;i<=n;i++)
        {
            int u,w;
            scanf("%d%d",&u,&w);
            if (i==1) s=u;
            mp[u][w]++; mp[w][u]++;
            in[w]++;
            in[u]++;
        }
        printf("Case #%d\n",TT);
        int ff=1;
        for (int i=1;i<=50;i++)    //点代表的是颜色，我们要判断所有的点 
            if (in[i]&1)
            {
                ff=0;
                break;
            }
        if (!ff)
           printf("some beads may be lost\n");
        else
        {
            for (int i=1;i<=50;i++)
                euler(i); 
        } 
        if (TT!=T) puts("");
    }
    return 0;
}

B - Guess

标签（空格分隔）： 拓扑排序

题目大意

对于一个序列a1，a2...an，我们可以计算出一个符号矩阵S，其中Sij为ai+..+aj的正负号。给出符号矩阵，要求输出一个对应的序列。

解题思路

使用连续和转化为前缀和之差的技巧，将前缀和当做一个顶点，那样就能确立边的关系，以及入度数，之后用拓扑排序求解，先着一个入度为0的顶点，删除其相关的边，循环操作。

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 105;
int N, A[maxn], C[maxn];
char S[maxn];
vector<int> G[maxn];
void addEdge(int u, int v) {
    C[v]++;
    G[u].push_back(v);
}
void solve () {
    int d = 0;
    queue<int> Q;
    for (int i = 0; i <= N; i++)
        if (C[i] == 0) Q.push(i);
    while (!Q.empty()) {
        int sz = Q.size();
        for (int k = 0; k < sz; k++) {
            int u = Q.front();
            Q.pop();
            A[u] = d;
            for (int i = 0; i < G[u].size(); i++) {
                int v = G[u][i];
                C[v]--;
                if (C[v] == 0)
                    Q.push(v);
            }
        }
        d++;
    }
}
int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%s", &N, S);
        memset(C, 0, sizeof(C));
        for (int i = 0; i <= N; i++) G[i].clear();
        int p = 0;
        for (int j = 0; j <= N; j++) {
            for (int i = j + 1; i <= N; i++) {
                if (S[p] == '+')
                    addEdge(j, i);
                else if (S[p] == '-')
                    addEdge(i, j);
                p++;
            }
        }
        solve();
        for (int i = 1; i <= N; i++) {
            printf("%d%c", A[i]-A[i-1], i == N ? '\n' : ' ');
        }
    }
    return 0;
}

C - Claw Decomposition

标签： 二分图判定

题目大意

 一张无向连通图，每个点连有三条边。询问是否可以将这个图分成若干个爪子，并满足条件：①每条边只能属于一个爪子②每个点属于几个爪子无所谓。输出YES/NO

解题思路

先对题目进行一下分析，要把原图分成若干个“爪”，而每个爪都有三条边，因为题目说明了每条边只能属于一个爪，所以图中边的总数应该是3的倍数，然后从每个点的度数为3，可以得到m*2 == n*3。（m为边数，n为点数），这是对图的边和点数量关系上先进行分析。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 300 + 5;
int color[maxn];
vector<int> G[maxn];
bool bipartite(int u){
    for(int i = 0;i < G[u].size();i++){
        int v = G[u][i];
        if(color[v] == color[u]) return false;
        if(!color[v]){
            color[v] = 3 - color[u];
            if(!bipartite(v)) return false;
        }
    }
    return true;
}
int main(){
    int n,m;
    while(scanf("%d",&n)){
        if(n == 0) break;
        int a,b;
        m = 0;
        memset(color,0,sizeof(color));
        for(int i = 0;i <= n;i++) G[i].clear();
        while(scanf("%d%d",&a,&b)){
            if(a == 0 && b == 0) break;
            G[a].push_back(b); G[b].push_back(a);
            m++;
        }
        color[1] = 1;//记得先把初始节点的color设为1
        if(m*2 == n*3 && bipartite(1))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

D - Cells

标签： 栈模拟DFS

题目大意

给一棵树，每次每次询问一个点是否是另一个点的祖先

解题思路

 我们思考一下深搜建树的过程，先遍历到一个父亲节点，再往下遍历到这个父亲节点的子节点，再往上回溯到该父亲节点。我们发现如果A是B的祖先，A的遍历时间点早于B的遍历时间点早于B的回溯时间点早于A的回溯时间点。
 也就是说我们如果给每个点建立两个时间值（类似Tarjan的思想，预计后天讲Tarjan），第一个时间值是遍历时间点，第二个时间值是回溯时间点，建树的时候预处理出来，那么对于每个询问，就可以O（1）得出结果了（判断一下四个值大小关系）。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<stack>
#define inf 0x7fffffff
using namespace std;
const int maxn=300000+10;
const int M = 20000000+100;
int n,m,pre[M],bac[M],vis[M],dfs_clock;
int an[maxn],c[maxn],sum;
stack<int> S;
void dfs()
{
    memset(vis,0,sizeof(vis));
    while (!S.empty()) S.pop();
    S.push(0);
    while (!S.empty())
    {
        int u=S.top() ;
        if (vis[u]==0)
        {
            vis[u]=1;
            pre[u]= ++dfs_clock;
            for (int i=an[u]+1 ;i<=an[u]+c[u] ;i++)
            {
                if (i<n) S.push(i);
                else {
                    pre[i]= ++dfs_clock;
                    bac[i]= ++dfs_clock;
                }
            }
        }
        else if (vis[u]==1)
        {
            bac[u]= ++dfs_clock;
            S.pop();
        }
    }
}
int main()
{
    int t,ncase=1;
    int ok=0;
    scanf("%d",&t);
    while (t--)
    {
        if (ok) printf("\n");ok=1;
        printf("Case %d:\n",ncase++);
        memset(pre,0,sizeof(pre));
        memset(bac,0,sizeof(bac));
        memset(an,0,sizeof(an));
        memset(c,0,sizeof(c));
        sum=0;
        dfs_clock=0;
        int a,b;
        scanf("%d",&n);
        for (int i=0 ;i<n ;i++)
        {
            scanf("%d",&c[i]);
            an[i]=sum;
            sum += c[i];
        }
        dfs();
        scanf("%d",&m);
        while (m--)
        {
            scanf("%d %d",&a,&b);
            if (pre[a]<pre[b] && bac[a]>bac[b]) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}