• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            poj 2672 Going from u to v or from v to u? 弱連通分量

            Going from u to v or from v to u?
            Time Limit: 2000MS Memory Limit: 65536K
            Total Submissions: 8032 Accepted: 1892

            Description

            In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?

            Input

            The first line contains a single integer T, the number of test cases. And followed T cases. 

            The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly. 

            Output

            The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.

            Sample Input

            1
            3 3
            1 2
            2 3
            3 1
            

            Sample Output

            Yes
            題目:給定一個圖,問你是否對于任意的定點對x,y,能找到一條從x到y 或從y到x的路徑,(滿足一條即可);
            類型:弱連通分量。
            解法:
            這題花了很長時間,至少花了兩個小時,到后來都想吐了,這讓我更惡心到了兩遍dfs求強連通分量的復雜。還好做出來了,雖然800+ms,還是挺爽的。
            n: 1000,  m: 6000
            原來什么都沒想就開始做,每次spfa(x,y),嘗試從x找到一條道y的路徑,果斷TLE。其實肯定TLE,不知道當時怎么想的。
            這題先求強連通分量,縮點,形成一棵新的樹,這樣主要是為了利用一些性質。若圖是弱連通的,縮點后的樹必須滿足一下性質:
            1,形成的是一棵樹:這是必須的。否則從一棵樹的點到另一棵樹無法到達。
            2,這棵樹有且僅有一個點的入度是0, 如果有多個的話那么這些入度為0的點是不可以互相到達的。
            3, 從這個入度為0的點進行dfs,找到的是一條鏈,就是不會有分叉,如果有的話,則兩個分叉的點互相不可達。
            (這點其實我不明白,應該是找條最長鏈的)
            代碼超級亂:
            
            

            Source Code

            Problem: 2762 User: hehexiaobai
            Memory: 9084K Time: 891MS
            Language: C++ Result: Accepted
            • Source Code
              #include<iostream>
                  #include<cstring>
                  #include<cstdio>
                  using namespace std;
                  const int MAXV = 1005;
                  const int MAXE = 6005;
                  int adj[MAXV][MAXV];
                  int adj_op[MAXV][MAXV];
                  int f[MAXV];
                  int sblg[MAXV];
                  int m, n, cntf,nstrong;
                  bool visit[MAXV];
                  bool strong[MAXV][MAXV];
                  int in[MAXV];
                  void dfs1(int u)
                  {
                  visit[u] = true;
                  for(int i = 1; i <= adj[u][0]; i ++)
                  if(!visit[adj[u][i]])dfs1(adj[u][i]);
                  f[cntf] = u;
                  cntf --;
                  }
                  void dfs2(int u, int nstrong)
                  {
                  visit[u] = true;
                  sblg[u] = nstrong;
                  for(int i = 1; i <= adj_op[u][0]; i ++)
                  if(!visit[adj_op[u][i]])dfs2(adj_op[u][i],nstrong);
                  }
                  bool flag ;
                  void dfs(int u)
                  {
                  visit[u] = true;
                  int c = 0;
                  for(int i = 1; i <= nstrong; i ++)
                  {
                  if(strong[u][i])
                  {
                  dfs(i);
                  c ++;
                  }
                  }
                  if(c > 1)flag = false;
                  }
                  int main()
                  {
                  int t,i,j, u, v;
                  scanf("%d",&t);
                  while(t--)
                  {
                  memset(adj,0,sizeof adj);
                  memset(f,0,sizeof f);
                  memset(adj_op, 0, sizeof (adj_op));
                  scanf("%d %d",&n, &m);
                  for(i = 0; i < m; i ++)
                  {
                  scanf("%d %d",&u, &v);
                  adj[u][0] ++;
                  adj[u][adj[u][0]] = v;
                  adj_op[v][0] ++;
                  adj_op[v][adj_op[v][0]] = u;
                  }
                  memset(visit, 0, sizeof visit);
                  cntf = n ;
                  for(i = 1; i <= n; i ++)
                  if(!visit[i]) dfs1(i);
                  memset(visit, 0, sizeof visit);
                  memset(sblg, 0, sizeof (sblg));
                  nstrong = 0;
                  for(i = 1; i <= n;i ++)
                  if(!visit[f[i]])
                  {
                  nstrong ++ ;
                  dfs2(f[i], nstrong);
                  }
                  if(nstrong == 1)
                  {
                  printf("Yes\n");
                  continue;
                  }
                  memset(in, 0, sizeof in);
                  memset(strong, 0,sizeof strong);
                  for( i  = 1; i <= n; i ++)
                  for(j = 1; j <= adj[i][0]; j++ )
                  if(sblg[i] != sblg[adj[i][j]])
                  {
                  in[sblg[adj[i][j]]] = true;
                  strong[sblg[i]][sblg[adj[i][j]]] = true;
                  }
                  int index = -1;
                  for(i = 1;i <= n; i ++)
                  if(in[sblg[i]] == false)
                  {
                  index = sblg[i];
                  break;
                  }
                  flag = true;
                  memset(visit, 0, sizeof visit);
                  dfs(index);
                  /*	for(i = 1; i <= nstrong; i ++,cout << endl)
                  for(j = 1; j <= nstrong; j ++)
                  cout << strong[i][j]<<' ';
                  */
                  for(i = 1; i <= nstrong;i ++)
                  if(visit[i] == false)
                  flag = false;
                  if(flag == true)
                  {
                  printf("Yes\n");
                  }
                  else printf("No\n");
                  }
                  return 0;
                  }

            posted on 2010-12-11 22:48 田兵 閱讀(639) 評論(0)  編輯 收藏 引用 所屬分類: 圖論題

            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            日日狠狠久久偷偷色综合0| 香港aa三级久久三级| A级毛片无码久久精品免费| 亚洲欧洲中文日韩久久AV乱码| 精品久久人人爽天天玩人人妻| 精品永久久福利一区二区| 狠狠色丁香婷婷综合久久来来去 | 狠狠色丁香久久婷婷综合_中 | 久久久精品久久久久久| 久久精品国产清自在天天线 | 亚洲精品乱码久久久久久自慰| 国产99久久精品一区二区| 久久久久免费视频| 国产人久久人人人人爽| 国产精品久久久久蜜芽| 精品久久久久久久久久久久久久久| 18岁日韩内射颜射午夜久久成人 | 久久伊人精品一区二区三区| 97精品伊人久久大香线蕉app| 亚洲伊人久久综合中文成人网| 精品久久久久香蕉网| 四虎久久影院| 久久国产精品国语对白| www.久久99| 国产V综合V亚洲欧美久久| 亚洲AV无码久久| 久久久久久国产精品无码下载| 色欲综合久久躁天天躁| 久久WWW免费人成—看片| 国产精品久久影院| 久久99久久99小草精品免视看| 国产人久久人人人人爽| 韩国免费A级毛片久久| 久久成人国产精品免费软件| 日韩精品无码久久一区二区三| 久久精品无码一区二区三区免费 | 麻豆AV一区二区三区久久| 久久精品中文无码资源站| 99精品国产免费久久久久久下载| 久久综合精品国产一区二区三区| 久久精品国产色蜜蜜麻豆|