المكونات المتصلة

في الرسم البياني غير الموجه، يُقال أن الرأسين \(u\) و \(v\) ينتميان إلى نفس المكون المتصل إذا كان هناك مسار يربط بينهما. إذا كان الرسم البياني يتكون من مكون واحد فقط، فإنه يُعتبر متصلاً.

Building Roads

Building Roads

CSES easy

يوجد \(n\) مدينة، و \(m\) طريقاً بينها. مهمتك هي إيجاد الحد الأدنى من عدد الطرق التي يجب إضافتها بحيث يكون هناك مسار بين أي مدينتين، وأيضاً تحديد أي الطرق يجب بناؤها.

Solution

الهدف هنا هو إضافة أحرف حتى يصبح الرسم البياني متصلاً. إذا أضفنا حرفاً يربط رؤوس نفس المكون، فإن المكونات الأخرى لن تتأثر، وإذا أضفنا حرفاً بين رؤوس مكونات مختلفة فإنها ستندمج.

إذا كان هناك \(C\) مكوناً فإننا بحاجة لإضافة \(C - 1\) حرفاً. هناك طرق عديدة لاختيار هذه الأحرف، طريقة بسيطة هي اختيار رأس عشوائي من المكون الأول وربطه برأس عشوائي من كل مكون من المكونات المتبقية.

const int maxN = 200'001;

bool vis[maxN];
vector<int> adj[maxN];

void dfs (int u) {
    vis[u] = true;

    for (int v : adj[u]) {
        if (!vis[v]) dfs(v);
    }
}

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

    for (int i = 0 ; i < m ; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> sources;

    for (int i = 1 ; i <= n ; i++) if (!vis[i]) {
        sources.push_back(i);
        dfs(i);
    }

    cout << sources.size() - 1 << endl;

    for (int i = 1 ; i < sources.size() ; i++) {
        cout << sources[0] << ' ' << sources[i] << endl;
    }
}

Cyclic Components

Cyclic Components

Codeforces easy

معطى رسم بياني غير موجه، احسب عدد المكونات التي هي دورات. مكون من \(k\) رأساً \(v_1, v_2, ..., v_k\) يُعتبر دورة إذا كان له بالضبط \(k\) حرفاً: \((v_1, v_2), (v_2, v_3), ..., (v_k, v_1)\).

Note

إذا كان هناك أي ترتيب للرؤوس يحقق الشرط أعلاه فإنها دورة.

Solution

إذا كان المكون دورة فإن جميع رؤوسه مجاورة لبالضبط \(2\) رأساً آخرين. في الواقع، هذا شرط كافٍ لتحديد ما إذا كان المكون دورة.

يمكن استخدام DFS لاستكشاف جميع رؤوس المكون للتحقق من هذا الشرط.

const int maxN = 200'001;

vector<int> adj[maxN];
bool vis[maxN];
 
bool dfs (int u) {
    vis[u] = 1;
    bool ret = (adj[u].size() == 2);
 
    for (int v : adj[u]) {
        if (!vis[v]) ret &= dfs(v);
    }
 
    return ret;
}
 
int main () { 
    int n, m;
    cin >> n >> m;
 
    for (int i = 0 ; i < m ; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    int ans = 0;
 
    for (int i = 1 ; i <= n ; i++) {
        if (!vis[i]) ans += dfs(i);
    }
    
    cout << ans << endl;
}