zl程序教程

您现在的位置是:首页 >  其它

当前栏目

D - Tying Rope

2023-09-27 14:28:34 时间

D - Tying Rope

https://atcoder.jp/contests/abc293/tasks/abc293_d

 

思路

/*
one rope model:
one end color -- rope number -- another end color
short form:
c -- r -- c

there are one critical condition:
for each rope, a end with same color cannot be tied multiple times.
so to speak, one end can only tie one time.

the condition make sure that there are only three shapes to be made:
(1) isolated rope, not tied to any other ropes
c -- r -- c

(2) line model, without cycle
c -- r -- c c -- r -- c c -- r -- c

(3) cycle model
c -- r -- c
c           c
\           \
\           \
r           r
\           \
\           \
c           c
c -- r -- c
*/

本题属于无向图,使用双向连接线表示一条连接,

对于任意两个绳子之间的打结, 可以保证, 只能可能形成,线 或者 环; 要么不打结。

对于未打结,度为0,即连线数目为0, 统计为 一个非环

对于线, 线的一端线段的度为2, 即其连线数目为2, 统计为一个非环

对于环,任意一个线段的度为4, 统计为一个环。

 

注意的是, 先统计完所有的 未打结, 或者 线的 情况;

然后再统计环的情况。

 

Code

https://atcoder.jp/contests/abc293/submissions/39762123

#include <iomanip>
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#include <limits.h>
#include <math.h>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };
int diry[8] = { 0, 1, -1, 0, -1, 1, -1, 1 };

#ifdef TESTING
#define DEBUG fprintf(stderr, "====TESTING====\n")
#define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define DEBUG
#define VALUE(x)
#define debug(...)
#endif

#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define FORD(a, b, c) for (int(a) = (b); (a) >= (c); --(a))
#define FORSQ(a, b, c) for (int(a) = (b); (a) * (a) <= (c); ++(a))
#define FORC(a, b, c) for (char(a) = (b); (a) <= (c); ++(a))
#define FOREACH(a, b) for (auto&(a) : (b))
#define REP(i, n) FOR(i, 0, n)
#define REPN(i, n) FORN(i, 1, n)
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a, b) memset(a, b, sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define PERMUTE next_permutation
#define TC(t) while (t--)

/******************************** COMMON FUNC START ***************************************/

LL quick_pow(LL x,LL n,LL m){
    LL res = 1;
    while(n > 0){
        if(n & 1)    res = res * x % m;
        x = x * x % m;
        n >>= 1;//相当于n=n/2.详情请参考位移运算符。
    }

    return res;
}

inline string IntToString(LL a)
{
    char x[100];
    sprintf(x, "%lld", a);
    string s = x;
    return s;
}

inline LL StringToInt(string a)
{
    char x[100];
    LL res;
    strcpy(x, a.c_str());
    sscanf(x, "%lld", &res);
    return res;
}

inline string GetString(void)
{
    char x[1000005];
    scanf("%s", x);
    string s = x;
    return s;
}

inline string uppercase(string s)
{
    int n = SIZE(s);
    REP(i, n)
    if (s[i] >= 'a' && s[i] <= 'z')
        s[i] = s[i] - 'a' + 'A';
    return s;
}

inline string lowercase(string s)
{
    int n = SIZE(s);
    REP(i, n)
    if (s[i] >= 'A' && s[i] <= 'Z')
        s[i] = s[i] - 'A' + 'a';
    return s;
}

inline void OPEN(string s)
{
#ifndef TESTING
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
#endif
}

/******************************** COMMON FUNC END ***************************************/

/******************************** GRAPH START ***************************************/
// Graph class represents a directed graph
// using adjacency list representation
class Graph {
public:
    map<int, bool> visited;
    map<int, list<int> > adj;

    // function to add an edge to graph
    void addEdge(int v, int w);

    // DFS traversal of the vertices
    // reachable from v
    void DFS(int v);
};

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

void Graph::DFS(int v)
{
    // Mark the current node as visited and
    // print it
    visited[v] = true;
    cout << v << " ";

    // Recur for all the vertices adjacent
    // to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFS(*i);
}

/******************************** GRAPH END ***************************************/

/*
https://atcoder.jp/contests/abcxxx/tasks/abcxxx_d
*/


int n, m;
map<int, vector<int> > e;
int vis[200005];
int dg[200005];
int ncc, cc; // non cycle count and cycle count

/*
one rope model:
one end color -- rope number -- another end color
short form:
c -- r -- c

there are one critical condition:
for each rope, a end with same color cannot be tied multiple times.
so to speak, one end can only tie one time.

the condition make sure that there are only three shapes to be made:
(1) isolated rope, not tied to any other ropes
c -- r -- c

(2) line model, without cycle
c -- r -- c c -- r -- c c -- r -- c

(3) cycle model
c -- r -- c
c           c
\           \
\           \
r           r
\           \
\           \
c           c
c -- r -- c
*/

void dfs(int i){
    vis[i] = true;
    
    for(auto next: e[i]){
        if (vis[next] == false){
            dfs(next);
        }
    }
}

int main()
{
    cin >> n >> m;

    for(int i=0; i<m; i++){
        int ai, bi;
        string aci, bci;
        cin >> ai >> aci >> bi >> bci;
        
        e[ai].push_back(bi);
        dg[ai]++;
        dg[bi]++;
        
        e[bi].push_back(ai);
        dg[ai]++;
        dg[bi]++;
    }

    for(int i=1; i<=n; i++){
        if (vis[i] == true){
            continue;
        }
        
        /*
        for (1) isolated rope
        this rope untie to any other ropes
        */
        if (dg[i] == 0){
            vis[i] = true;
            ncc++;
        /*
        for (2) line model, the rope is start end
        */
        } else if (dg[i] == 2){
            dfs(i);
            ncc++;
        }
    }


    for(int i=1; i<=n; i++){
        if (vis[i] == true){
            continue;
        }

        /*
        for (3) line model, the rope is start end
        */
        if (dg[i] == 4){
            dfs(i);
            cc++;
        }
    }

    cout << cc << " " << ncc << endl;

    return 0;
}