SAFENET2 spoj - Mạng máy tính an toàn

Nguồn đề bài: http://vn.spoj.com/problems/SAFENET2/

1. Đề bài SAFENET2 spoj

Có n máy tính đánh số từ 1 đến n và m dây cáp mạng,giữa 2 máy tính có thể có một hoặc nhiều đường dây cáp mạng nối chúng,không có cáp mạng nối một máy với chính nó.Hai máy tính có thể truyền dữ liệu cho nhau nếu có đường cáp nối trực tiếp giữa chúng hoặc truyền qua một số máy trung gian.

Một tập S các máy tính được gọi là hệ thống an toàn nếu dù một máy tính bất kỳ bị tấn công (do sự tò mò của người dân :-(,cứ thích truy cập và hack những trang cấm 🙁 ) thì trong số những máy tính còn lại,những máy tính thuộc tập S vẫn có thể truyền được dữ liệu cho nhau. Xác định số lượng lớn nhất có thể các máy tính của tập S

Input

-Dòng 1 chứa 2 số nguyên n,m(1<=n<=30.000,0<=m<=100.000)

-m dòng tiếp theo ghi thông tin về các dây cáp mạng,gồm 2 chỉ số của 2 máy được dây đó nối trực tiếp

Output

Ghi một số nguyên duy nhất là số lượng máy tính lớn nhất tìm đc

Example

Input:
8 10
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 8
8 1
Output:
4

2. Hướng dẫn SAFENET2 spoj

Trước khi làm bài này, ta sẽ tìm hiểu về cấu tạo của đồ thị vô hướng. Đồ thị vô hướng chia thành các thành phần song liên thông. Các thành phần song liên thông được nối với nhau bởi các cầu.

hình ảnh tượng trưng

safenet: tập an toàn —— S là safenet -> song lt

——–S là song lt -> chưa chắc đã an toàn

=> N xét: mỗi tp song lt đc cấu tạo bởi các tập an toàn, gắn vs nhau qua các khớp.

=> ???? làm thế nào để tìm đc S?

num là số thự tự duyệt trong dfs
gọi low of 1 đỉnh là số hiệu nhỏ nhất of đỉnh kề vs đỉnh đó có num >= nó

u có 3 loại con:

low[v2]>num[u]:có 1 S với số đỉnh bằng số con of v2.
low[v3]=num[u]: có 1 S với số đỉnh bằng số con of v3+1 (đỉnh u).
low[v1]<num[u].

3. Code tham khảo SAFENET2 spoj

#include <bits/stdc++.h>
#define maxn 30001
#define maxm 100005
#define fs first
#define sc second
using namespace std;
typedef pair<int,int> II;
    int n,m,deg[maxn];
    vector<int> g[maxn];
    II ed[maxm];
    int s[maxn],cur[maxn],cl[maxn],pe[maxn],pre[maxn],num[maxn],low[maxn],x[maxn],id=0;
    int sl[maxn];
void dfs(int xp)
{
    int sn=0;
    s[++sn]=xp; cl[xp]=1;
    pe[xp]=pre[xp]=0;
    num[xp]=low[xp]=++id;
    x[id]=xp;
    while(sn)
    {
        int u=s[sn];
        if(cur[u]<deg[u])
        {
            int i=g[u][cur[u]++];
            if(abs(i)!=pe[u])
            {
                int v=(i>0)?ed[i].sc:ed[-i].fs;
                if(cl[v]==0)
                {
                    cl[v]=1; s[++sn]=v;
                    pe[v]=abs(i); pre[v]=u;
                    num[v]=low[v]=++id;
                    x[id]=v;
                } else low[u]=min(low[u],num[v]);
            }
        } else
        {
            int w=pre[u];
            if(w) low[w]=min(low[w],low[u]);
            --sn;
        }
    }
}
int main()
{
    //freopen("safenet.inp","r",stdin);
    //freopen("safenet.out","w",stdout);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int u,v;
        cin>>u>>v;
        ed[i]=II(u,v);
        deg[u]++; g[u].push_back(i);
        deg[v]++; g[v].push_back(-i);
    }
    for(int i=1; i<=n; i++)
        if(cl[i]==0) dfs(i);
    int ds=1;
    for(int j=n; j>=1; j--)
    {
        int u=x[j];
        for(int o=0; o<deg[u]; o++)
        {
            int i=g[u][o];
            int v=(i>0)? ed[i].sc:ed[-i].fs;
            if(abs(i)!=pe[v]) continue;
            if(sl[v]==0) continue;
            if(low[v]==num[u])
            {
                ds=max(ds,sl[v]+1);
                sl[v]=0;
            }
            else
            if(low[v]>num[u])
            {
                ds=max(ds,sl[v]+1);
                sl[v]=0;
            } else sl[u]+=sl[v];
        }
        sl[u]++;
    }
    cout<<ds;
}

nguồn: kienthuc24h.com-

SAFENET2 spoj – Mạng máy tính an toàn