MESSAGE Spoj – Truyền tin
Một lớp gồm N học sinh, mỗi học sinh cho biết những bạn mà học sinh đó có thể liên lạc được (chú ý liên lạc này là liên lạc một chiều : u có thể gửi tin tới v nhưng v thì chưa chắc đã có thể gửi tin tới u).Thầy chủ nhiệm đang có một thông tin rất quan trọng cần thông báo tới tất cả ...
Một lớp gồm N học sinh, mỗi học sinh cho biết những bạn mà học sinh đó có thể liên lạc được (chú ý liên lạc này là liên lạc một chiều : u có thể gửi tin tới v nhưng v thì chưa chắc đã có thể gửi tin tới u).Thầy chủ nhiệm đang có một thông tin rất quan trọng cần thông báo tới tất cả các học sinh. Để tiết kiệm thời gian, thầy chỉ nhắn tin tới 1 số học sinh rồi sau đó nhờ các học sinh này nhắn lại cho tất cả các bạn mà các học sinh đó có thể liên lạc được, và cứ lần lượt như thế làm sao cho tất cả các học sinh trong lớp đều nhận được tin .
Hãy tìm một số ít nhất các học sinh mà thầy chủ nhiệm cần nhắn.
Input
– Dòng đầu là N, M (N <= 10^6,M là số lượng liên lạc 1 chiều)
– Một số dòng tiếp theo mỗi dòng gồm 2 số u , v cho biết học sinh u có thể gửi tin tới học sinh v
Output
– Gồm 1 dòng ghi số học sinh cần thầy nhắn tin.
Example
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | Input: 12 15 1 3 3 6 6 1 6 8 8 12 12 9 9 6 2 4 4 5 5 2 4 6 7 10 10 11 11 7 10 9 <b>Output:</b> 2 |
Chọn các học sinh 7 và 2.
Thuật toán:
coi mỗi học sinh là 1 đỉnh,mỗi đường liên lạc 1 chiều là 1 cung có hướng của đồ thì.ta có nhận xét:
nếu ta truyền tin cho bất kì 1 đỉnh nào trong thành phần liên thông mạnh X thì tất cả những đỉnh thuộc thành phần liên thông mạnh đó và những thành phần liên thông mạnh Y(có u->v với u thuộc x và v thuộc Y) đều nhận đc thông tin.
Do đó ta sử dụng thuật toán tarjan để tìm các thành phần liên thông mạnh.Sau đó ta dùng mảng dd để đánh dấu với ý nghĩa nếu dd[i]=1 thì thành phần liên thông mạnh i k phải truyền tin vào bất kì 1 đỉnh nào cả.Để làm được điều này ta duyệt qua tất cả các cung có hướng u->v.nếu lt[u]!=lt[v] thì gán dd[v]=1.^.^
Code tham khảo MESSAGE Spoj – Truyền tin:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include <bits/stdc++.h> #define maxn 1000001 #define x first #define y second using namespace std; typedef pair < int , int > II; II e[maxn]; vector < int > g[maxn]; int n,m,deg[maxn],cl[maxn],low[maxn],num[maxn],s[maxn],sn=0,id=0,d[maxn],slt=0,lt[maxn]; void doc() { cin>>n>>m; for(int i=1;i<=m;i++) { int u,v; cin>>u>>v; e[i]=II(u,v); deg[u]++; g[u].push_back(v); } } void dfs(int u) { cl[u]=1; s[++sn]=u; low[u]=num[u]=++id; for(int i=0;i<deg[u];i++) { int v=g[u][i]; if(cl[v]==0) { dfs(v); low[u]=min(low[u],low[v]); }else if(cl[v]==1)low[u]=min(low[u],num[v]); } if(low[u]==num[u]) { slt++; int v; do { v=s[sn--]; lt[v]=slt; cl[v]=2; }while(v!=u); } } void tinh() { for(int i=1;i<=n;i++) if(cl[i]==0) dfs(i); for(int i=1;i<=m;i++) { int u=e[i].x,v=e[i].y; if(lt[u]!=lt[v]) d[lt[v]]=1; } int dem=0; for(int i=1;i<=slt;i++) if(d[i]==0) dem++; cout<<dem; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); doc(); tinh(); } |
