البحث في العمق

هذه خوارزمية تستكشف بشكل تكراري جيران رأس معين حتى تتم زيارة جميع الرؤوس. الرأس الابتدائي يسمى المصدر.

كيف يعمل DFS

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

التعقيد الزمني لهذا الاجتياز هو \(O(N + M)\) حيث \(N\) هو عدد الرؤوس و \(M\) هو عدد الأحرف.

const int maxN = 200'001;

bool vis[maxN];
vector<int> adj[maxN]; // adjacency list

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

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

Path Finding

Path Finding

easy

معطى رسم بياني غير موجه \(G\) يتكون من \(N\) رأساً مرقمة من \(1\) إلى \(N\) و \(M\) حرفاً، تحقق مما إذا كان الرأس \(1\) يمكنه الوصول إلى الرأس \(N\) واطبع مساراً ممكناً.

Solution

إذا بدأنا اجتياز DFS على الرأس \(1\)، يمكننا فحص vis[N] لمعرفة ما إذا كان المسار موجوداً أم لا. هدفنا هو استرجاع المسار الذي اتخذه الاجتياز للوصول إلى الرأس \(N\).

لتحقيق ذلك، سنخزن مصفوفة \(p\) حيث \(p_i\) هو الرأس الذي أدى بـ DFS لاكتشاف الرأس \(i\). باستخدام هذا يمكننا تتبع المسار من \(N\) عائدين إلى \(1\).

const int maxN = 200'001;
int vis[maxN], p[maxN];
vector<int> adj[maxN];

void dfs (int u) {
    vis[u] = true;
    for (int v : adj[u]) {
        if (!vis[v]) {
            p[v] = u; // we discovered v through u
            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);
    }

    dfs(1);

    if (!vis[n]) cout << "No";
    else {
        cout << "Yes\n";

        vector<int> pth;
        for (int i = n ; i != 1 ; i = p[i]) { // trace back loop 
            pth.push_back(i);  
        }

        reverse(pth.begin(), pth.end());
        cout << 1 << ' '; 
        for (int i : pth) cout << i << ' ';
    }
}

Building Teams

Building Teams

CSES easy

يوجد \(N\) تلميذاً في الصف، و \(M\) صداقة بينهم. مهمتك هي تقسيم التلاميذ إلى فريقين بحيث لا يكون أي تلميذين في فريق واحد صديقين. يمكنك اختيار أحجام الفرق بحرية.

Solution

Tip

إنها حيلة مفيدة أن تحاول تصور العلاقات الثنائية كرؤوس وأحرف.

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

نلاحظ أنه يجب علينا تعيين لون لكل رأس (مثلاً إما أحمر أو أزرق) بحيث تكون نقاط نهاية كل حرف بألوان مختلفة. هذا يُعرف بـ التلوين الثنائي.

لأي تعيين صالح، إذا قلبنا لون كل رأس من أحمر إلى أزرق أو العكس، سيظل التعيين صالحاً، لذا يمكننا افتراض أن الرأس \(1\) دائماً أحمر.

من ذلك يمكننا ملاحظة أن جميع جيرانه يجب أن يكونوا أزرق وبشكل تكراري يمكننا تعيين ألوان لجميع الرؤوس.

Important

إذا لونا رأساً بلون \(C\) ثم اكتشفنا أننا سبق ولونا أحد جيرانه \(C\) أيضاً فيجب علينا التوقف فوراً لأننا وجدنا تناقضاً.

قد يتكون الرسم البياني من عدة مكونات منفصلة لذا يجب علينا الحل لكل واحدة على حدة.

const int maxN = 200'001;

bool vis[maxN], clr[maxN], contradiction = false;
vector<int> adj[maxN];

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

    for (int v : adj[u]) {
        if (vis[v]) {
            if (clr[v] == clr[u]) contradiction = true;
        } else {
            clr[v] = !clr[u];
            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);
    }

    for (int i = 1 ; i <= n ; i++) if (!vis[i]) dfs(i);

    if (contradiction) cout << "IMPOSSIBLE";
    else {
        for (int i = 1 ; i <= n ; i++) cout << 1 + clr[i] << ' ';
    }
}