30pts,Orz dalao

斯茂 @ 2018-10-06 11:30:37

#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
char a, b;
int dfn[20005], low[20005], color[20005], cnt, clr;
bool vis[205];
stack <int> s;
vector <int> V[20005];
void tarjan(int x)
{
  int i, r;
  dfn[x] = low[x] = ++cnt;
  vis[x] = 1;
  s.push(x);
  for(i = 0; i < V[x].size(); i++)
  {
    r = V[x][i];
    if(!dfn[r])
    {
      tarjan(r);
      low[x] = min(low[x], low[r]); 
    }
    else
      if(vis[r])
        low[x] = min(low[x], dfn[r]);
  }
  if(low[x] == dfn[x])
  {
    color[x] = ++clr;
    vis[x] = 0;
    while(s.top() != x)
    {
      color[s.top()] = clr;
      vis[x] = 0;
      s.pop();
    }
    s.pop();
  }
}
int main(int argc, char **argv)
{
    int T;
    int m, n, i;
    int x, y, z, w;
    bool f;
    cin >> T;
    while(T--)
    {
      cin >> n >> m;
      for(i = 1; i <= n; i++)
        V[i].clear();
      memset(dfn, 0, sizeof(dfn));
      memset(low, 0, sizeof(low));
      memset(vis, 0, sizeof(vis));
      memset(color, 0, sizeof(color));
      cnt = clr = 0;
      for(i = 1; i <= m; i++)
      {
        cin >> a >> x >> b >> z;
        y = (a != 'm');
        w = (b != 'm');
        V[2 * x - !y].push_back(2 * z - w);
        V[2 * z - !w].push_back(2 * x - y);
      }
      for(i = 1; i <= 2 * n; i++)
        if(!dfn[i])
        {
          while(s.size()) s.pop();
          tarjan(i);
        }
      f = 1;
      for(i = 1; i <= n; i++)
        if(color[2 * i - 1] == color[2 * i])
          f = 0;
      if(f)
        cout << "GOOD" << endl;
      else
        cout << "BAD" << endl; 
    }
    return 0;
}

by AzusaCat @ 2018-10-06 11:32:24

orz

by miaojiexi @ 2018-10-06 11:37:41

@韩沛煊 并不会tarjain

by PIG集团总经理 @ 2018-10-06 11:45:53

orz

by 斯茂 @ 2018-10-06 12:48:52

#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
char a, b;
int dfn[20005], low[20005], color[20005], cnt, clr;
bool vis[205];
stack <int> s;
vector <int> V[20005];
void tarjan(int x)
{
  int i, r;
  dfn[x] = low[x] = ++cnt;
  vis[x] = 1;
  s.push(x);
  for(i = 0; i < V[x].size(); i++)
  {
    r = V[x][i];
    if(!dfn[r])
    {
      tarjan(r);
      low[x] = min(low[x], low[r]); 
    }
    else
      if(vis[r])
        low[x] = min(low[x], dfn[r]);
  }
  if(low[x] == dfn[x])
  {
    color[x] = ++clr;
    vis[x] = 0;
    while(s.top() != x)
    {
      color[s.top()] = clr;
      vis[x] = 0;
      s.pop();
    }
    s.pop();
  }
}
int main(int argc, char **argv)
{
    int T;
    int m, n, i;
    int x, y, z, w;
    bool f;
    cin >> T;
    while(T--)
    {
      cin >> n >> m;
      for(i = 1; i <= 2 * n; i++)
        V[i].clear();
      memset(dfn, 0, sizeof(dfn));
      memset(low, 0, sizeof(low));
      memset(vis, 0, sizeof(vis));
      memset(color, 0, sizeof(color));
      cnt = clr = 0;
      for(i = 1; i <= m; i++)
      {
        cin >> a >> x >> b >> z;
        y = (a != 'm');
        w = (b != 'm');
        V[2 * x - !y].push_back(2 * z - w);
        V[2 * z - !w].push_back(2 * x - y);
      }
      for(i = 1; i <= 2 * n; i++)
        if(!dfn[i])
        {
          while(s.size()) s.pop();
          tarjan(i);
        }
      f = 1;
      for(i = 1; i <= n; i++)
        if(color[2 * i - 1] == color[2 * i])
          f = 0;
      if(f)
        cout << "GOOD" << endl;
      else
        cout << "BAD" << endl; 
    }
    return 0;
}

现在70了......

by 斯茂 @ 2018-10-06 13:18:34

solved,

by 斯茂 @ 2018-10-06 13:20:43

tarjan打错了