【強連通分量】四面楚歌 virus 解題報告

【題目描述】

公元2008年10月31日星期五，篤志者所在的整個機房由於猖獗的病毒一片恐慌。經查證，病毒是由A1機器散播開來的。。這要追溯到29日，篤志者由於病毒被迫從A1機器撤離。

一想到病毒是從自己的機器傳開的，篤志者就心神不寧。他決定搞清楚病毒是怎麼散播開來的。事實上，機房內的機器並不是全部都能夠互相感染的。篤志者（ceeji）好不容易經過測試得到了機房中各機器間是否連通的圖表，就在他馬上就要得出結果的時候，大腦突然亂了！問題的嚴重性在於：如果他不在1s內搞清楚這個問題，機房就會整體癱瘓。現在篤志者求助於你，他需要知道病毒從未感染機房開始，最少入侵幾臺機器之後，機房就會整體感染。

【輸入格式】

文件的第一行為一個整數n，第二行至第n+1行為n*n的矩陣（若第i行第j列為1，則機器i能對機器j進行ARP攻擊（即感染機器j），若第i行第j列為0，則機器i不能感染機器j）。

文件名為“2.in”。

【輸出格式】

輸出文件只有一行，為篤志者想知道的最少感染機器數。

文件名為“2.out”。

 

【輸入樣例】

8

0 0 1 0 0 0 0 0

1 0 0 1 0 0 0 0

0 1 0 1 1 0 0 0

0 0 0 0 0 1 0 0

0 0 0 1 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 1 0 0 0 1

0 0 0 0 0 0 1 0

【輸出樣例】

2

【資料範圍】

對於 100% 的資料，n<=1000

【分析】

經典的圖論，求所有強連通分量並縮點進行拓撲排序，入度為0的點即為所求。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25678

001 /*
002 *Problem:“一家人杯”模擬賽比賽環境適應賽 四面楚歌 virus
003 *Author: Yee-fan Zhu
004 *Website: http://www.yeefanblog.tk/
005 */
006 #include <cstdio>
007 #include <cstdlib>
008 #include <vector>
009 #include <stack>
010 using namespace std;
011 typedef vector<int> Vec;
012 const int MAXN=1001;
013 Vec Map[MAXN];
014 int Flag[MAXN][MAXN];
015 int N;
016 int Dfn[MAXN];
017 int Low[MAXN];
018 int InStack[MAXN];
019 int Belong[MAXN];
020 int Scc[MAXN];
021 int Index=0;
022 int SCC=0;
023 stack<int> S;
024
025 /*
026 *學習資料：http://www.byvoid.com/blog/scc-tarjan/
027 */
028
029 void init()
030 {
031     scanf("%d\n",&N);
032     int x;
033     for(int i=1;i<=N;i++)
034     {
035         Dfn[i]=0,Low[i]=0;
036         Belong[i]=0,InStack[i]=0;
037         Scc[i]=0;
038         for(int j=1;j<=N;j++)
039         {
040             scanf("%d",&x);
041             if(x==1)
042             {
043                 Map[i].push_back(j);Flag[i][j]=1;
044             }
045         }
046     }
047 }
048
049 int Min(int a,int b)
050 {return a<b?a:b;}
051
052 void Targan(int u)
053 {
054     Dfn[u]=Low[u]=++Index;
055     S.push(u);
056     InStack[u]=1;
057     int v;
058     for(unsigned int i=0;i<Map[u].size();i++)
059     {
060         v=Map[u][i];
061         if(Dfn[v]==0)
062         {
063             Targan(v);
064             Low[u]=Min(Low[u],Low[v]);
065         }
066         else if(InStack[v]==1)
067         {
068             Low[u]=Min(Low[u],Dfn[v]);
069         }
070     }
071     int tmp;
072     if(Dfn[u]==Low[u])
073     {
074         SCC++;
075         do
076         {
077             tmp=S.top();
078             S.pop();
079             Belong[tmp]=SCC;
080             InStack[tmp]=0;
081         }while(u!=tmp);
082     }
083 }
084
085 int main()
086 {
087     freopen("virus.in","r",stdin);
088     freopen("virus.out","w",stdout);
089     init();
090     for(int i=1;i<=N;i++) { if(Dfn[i]==0) Targan(i);}
091     int Ans=0;
092     for(int i=1;i<=N;i++)
093     {
094         for(int j=1;j<=N;j++)
095         {
096             if(Flag[i][j]==1 && Belong[i]!=Belong[j])
097                 Scc[Belong[j]]=1;
098         }
099     }
100     for(int i=1;i<=SCC;i++)
101         if(Scc[i]==0) Ans++;           
102     printf("%d\n",Ans);
103     return 0;
104 }