読者です 読者をやめる 読者になる 読者になる

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

タスクが増えるとすべてがおろそかになるクセを直したい

うん。

2491

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct hash {
    vector<string> key;
    int find(string str) {
        for (int i=0; i<key.size(); i++) {
            if (key[i]==str) return i;
        }
        key.push_back(str);
        return key.size()-1;
    }
    string fstr(int k) {
        return key[k];
    }
};
int es[333], s;
bool used[333];
vector<string> root;
bool dfs(int x, int cnt, hash *h) {
    root.push_back((*h).fstr(x));
    used[x]=true;
    cnt++;
    if (es[x]==-1&&cnt==s) return true;
    else if (es[x]==-1) return false;
    if (used[es[x]]) return false;
    return dfs(es[x],cnt,h);
}
int main() {
    int t; scanf("%d",&t);
    for (int ix=1; ix<=t; ix++) {
        scanf("%d",&s);
        hash h;
        memset(es, -1, sizeof(es));
        for (int i=0; i<s-1; i++) {
            string s1, s2; cin>>s1>>s2;
            es[h.find(s1)]=h.find(s2);
        }
        for (int i=0; i<s; i++) {
            root.clear();
            memset(used, 0, sizeof(used));
            if (dfs(i,0,&h)) {
                cout<<"Scenario #"<<ix<<":"<<endl;
                for (int j=0; j<root.size(); j++) cout<<root[j]<<endl;
                cout<<endl;
                break;
            }
        }
    }
}

2492

#include <cstdio>
#include <iostream>
using namespace std;
struct unionfind {
    int par[6000], rank[6000];
    void init(int n) {
        for (int i=0; i<n; i++) {
            par[i]=i;
            rank[i]=0;
        }
    }
    int find(int x) {
        if (par[x]==x) return x;
        return par[x]=find(par[x]);
    }
    void unite(int x, int y) {
        x=find(x); y=find(y);
        if (x==y) return;
        if (rank[x]<rank[y]) par[x]=y;
        else {
            par[y]=x;
            if (rank[x]==rank[y]) rank[x]++;
        }
    }
    bool same(int x, int y) {
        return find(x)==find(y);
    }
};
int t, b, s;
unionfind uf;
int main() {
    scanf("%d",&t);
    for (int ix=1; ix<=t; ix++) {
        scanf("%d%d",&b,&s);
        uf.init(b*2);
        bool flag=true;
        for (int i=0; i<s; i++) {
            int a1, a2; scanf("%d%d",&a1,&a2); a1--; a2--;
            if (uf.same(a1,a2)||uf.same(a1+b,a2+b)) flag=false;
            uf.unite(a1,a2+b); uf.unite(a1+b,a2);
        }
        printf("Scenario #%d:\n",ix);
        if (flag) puts("No suspicious bugs found!");
        else puts("Suspicious bugs found!");
        puts("");
    }
}