Đường Mới Trong vương quốc có nn thành phố và hiện có mm đường thương mại. Mỗi đường thương mại nối trực tiếp hai thành phố và là đường một chiều. Thương nhân mang hàng hóa đi bán ở các thành phố khác và sẽ là tốt nhất nếu anh ta mua được hàng hóa mới và trở về thành phố của mình không phải với chiếc xe ngựa rỗng. Dĩ nhiên, khi đó vì mục đích an toàn, anh ta phải quay về bằng đường thương mại. Nếu từ aa có thể tới bb theo các con đường thương mại và từ bb có thể trở về aa cũng theo các con đường thương mại thì aa và bb là hai thành phố thân thiện. Để giảm bớt nỗi cực nhọc của các thương nhân bình dân, chính phủ cho sửa sang lại các tuyến thương mại hiện có và cho xây dựng thêm một số đường thương mại mới. Tuy vậy, với ngân khố quốc gia hạn chế, nhà vua quyết định chỉ mở thêm các đường thương mại nối các thành phố thân thiện và không trùng lặp với các đường hiện có, sao cho giữa các thành phố thân thiện có đường nối trực tiếp với nhau. Yêu cầu: Cho n,mn,m và mạng đường thương mại hiện có. Không có đường nào nối một thành phố với chính nó. Xác định số đường mới tối thiểu cần xây dựng thêm? Mô tả đầu vào Dòng đầu tiên chứa hai số nguyên nn và mm. Mỗi dòng trong mm dòng tiếp theo chứa hai số nguyên aa và bb – một đường thương mại đi trực tiếp từ aa tới bb. Ràng buộc 1≤n≤10^51≤n≤10 5 . 0≤m≤2×10^50≤m≤2×10 5 . Subtask 11 (60%60% số điểm): 1≤n≤1001≤n≤100. Subtask 22 (40%40% số điểm): Không có ràng buộc gì thêm. Mô tả đầu ra Một số nguyên duy nhất là kết quả tìm được. Test case mẫu Đầu vào mẫu 1 3 3 1 2 2 3 3 1 Đầu ra mẫu 1 3

Cách giải: u tới được v và v cũng tới được u thì u, v thuộc 1 tplt mạnh (scc).

số cạnh để nối hết các đỉnh trong 1 tplt mạnh là: Gọi n là số đỉnh trong tplt mạnh đó 

=> số cạnh n*(n - 1) (quy tắc nhân).

Nhưng trong tplt đó đã có sẵn x cạnh nên đáp án cho tplt đó là n - x.

Như vậy đáp án chính là tổng cách cạnh có thể tạo ra của các tplt mạnh.

Lưu ý: Vì đề cho cạnh trùng nên dẫn tới việc tính sai nên ta cần thêm bước khử cạnh trùng:
Link code: ideone.com/VEMdQD

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int MAXN = 1e5 + 7;
int low[MAXN], id[MAXN], dfstime, scc[MAXN], cnt, ans, save[MAXN], node[MAXN];
int n, m;
bool mark[MAXN];
vector <int> a[MAXN];
set <int> s[MAXN];
stack <int>st;
void dfs(int u){
    low[u] = id[u] = ++dfstime;
    st.push(u);
    for(auto v : a[u]){
        if(!mark[v]){
            if(!id[v]){
                dfs(v);
                low[u] = min(low[v], low[u]);
            }
            else low[u] = min(low[u], id[v]);
        }
    }
    if(low[u] == id[u]){
        int v;
        cnt++;
        do{
            v = st.top();
            st.pop();
            scc[v] = cnt;
            mark[v] = 1;
            node[cnt]++;
        }while(u != v);
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        if(s[x].find(y) == s[x].end()){
            a[x].push_back(y);
            s[x].insert(y);
        }
    }
    for(int i = 1; i <= n; i++) if(!id[i])dfs(i);
    
    for(int u = 1; u <= n; u++)
        for(auto v : a[u])
            if(scc[u] == scc[v]) save[scc[v]]++;
        
    for(int i = 1; i <= cnt; i++){
        int cur = node[i];
        cur = (cur * (cur - 1));
        ans += cur - save[i];
    }
    cout << ans;
}

-----------------------------

**Xin 5* ạ**