1816. 连通

include

#define FUCK ios::sync_with_stdio(false);
using namespace std;
vector<int>G[1000005];
int visited[1000005]={0};
void dfs(int i)
{
        if(visited[i]==1) return;
        else{
                visited[i]=1;
                for(int j=0;j<G[i].size();j++){
                        dfs(G[i][j]);
                }
        }
}
int main()
{
        FUCK;cin.tie(0);
        int n,m;cin>>n>>m;
        memset(visited,0,sizeof(visited));
        for(int i=0;i<m;i++){
                int a,b;cin>>a>>b;
                G[a].push_back(b);
                G[b].push_back(a);
        }
        dfs(1);
        for(int i=1;i<=n;i++){
                if(visited[i]==0){
                        cout<<"no";
                        return 1e9;
                }
        }
        cout<<"yes";
}

可能上述问题主要出在第一次我用了（u,v,w）写的，每次遍历边开销巨大，但第二次我用了邻接矩阵，直接编译错误了…

include

include

using namespace std;

define max_size 100010

int map[max_size][max_size];
bool visited[max_size];
int n,m;
queueq;

void bfs(int u0)
{
visited[u0]=true;
q.push(u0);

while(!q.empty()){
    for(int i=1;i<=n;i++) {
        if(!visited[i]&&map[q.front()][i]==1){
            q.push(i);
            visited[i]=true;
        }
    }
    q.pop();
}

}

int main()
{
cin>>n>>m;

int u,v;
for(int i=1;i<=m;i++){
    cin>>u>>v;
    map[u][v]=1;
    map[v][u]=1;
}
for(int i=1;i<=n;i++)
    visited[i]=false;

bfs(1);

bool flag=true;
for(int i=1;i<=n;i++)
    if(!visited[i])
        flag=false;

if(flag)
    cout<<"yes";
else
    cout<<"no";

return 0;

}

include

include

using namespace std;
vector > v;
vector visit;
int cnt = 0;
void dfs(int i) {
cnt++;
visit[i] = 1;
for (int j = 0;j < v[i].size();j++) {
if (visit[v[i][j]] == 0) dfs(v[i][j]);
}
}
int main() {
int n, m, a, b;
scanf(“%d%d”, &n, &m);
v.resize(n + 1);
visit.resize(n + 1);
for (int i = 0;i < m;i++) {
scanf(“%d%d”, &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1);
if (cnt == n) printf(“yes”);
else printf(“no”);
return 0;
}

我用的dfs

define _CRT_SECURE_NO_WARNINGS

include

include

using namespace std;
bool visit[100005] = { false };
struct link {
int data;
struct link* next;
};

struct map {
int v, e;
link list[100005];
};

map create(int v, int e) {
map s = new map;
s->v = v;
s->e = e;
for (int i = 0; i < 100005; i++)
s->list[i].next = NULL;
for (int i = 0; i < e; i++) {
int start, end;
cin >> start >> end;
link* a = new link;
a->data = end;
a->next = s->list[start].next;
s->list[start].next = a;
}
return s;
}

void dfs(map s, int n, int& count) {
link temp;
count++;
visit[n] = true;
temp = s->list[n].next;
while (temp) {
if (!visit[temp->data])
dfs(s, temp->data, count);
temp = temp->next;
}
}

int main() {
int n, m, count = 0;
cin >> n >> m;
map* s = create(n, m);
dfs(s, 1, count);
if (count == n)
cout << “yes” << endl;
else
cout << “no” << endl;
return 0;
}

DFS一遍之后，遍历一遍访问数组，若结点都访问过则输出yes，存在结点没被访问则输出no。set用来保存输入的结点，采用邻接表存储（邻接矩阵不适合，太大了）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
int n;      //定点数 
vector<int> Adj[maxn];
bool vis[maxn]={false};     //访问标记 
unordered_set<int> se;

void dfs(int u) {
    vis[u] = true;
    for(int i = 0;i < Adj[u].size();i++) {
        int v = Adj[u][i];
        if(!vis[v])
            dfs(v);
    }   
}

int main() {
    int m;cin>>n>>m;
    int u,v;
    for(int i = 0;i < m;i++) {
        cin>>u>>v;
        se.insert(u);se.insert(v);
        Adj[u].push_back(v);
        Adj[v].push_back(u);
    }
    dfs(u);     //从最后一条边输入的点开始dfs
    bool flag = true;   //默认都遍历过 
    for(auto it = se.begin();it != se.end();it++) {
        if(vis[*it]==false) flag = false;
        it++;
    }
    if(flag) cout<<"yes";
    else cout<<"no";
    return 0;
}

我觉得 EOJ 应该出个告示讲一讲 Markdown 的存在，不然大家可能不知道为什么自己发的帖子格式总是不对 Orz。

这道题是 dfs 判断连通的经典题。不过，因为它只让我们判断连通，所以其实还可以（~~水一把~~）直接用 Union_find。

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

class Union {
    vector<unsigned> roots;
    unsigned tree_cnt;

    unsigned find_root(unsigned a) {
        if (roots[a] == a)
            return a;
        return roots[a] = find_root(roots[a]);
    }

  public:
    Union(unsigned n) : roots(vector<unsigned>(n + 1)), tree_cnt(n) {
        iota(roots.begin(), roots.end(), 0);
    }

    void connect(unsigned a, unsigned b) {
        unsigned at = find_root(a);
        unsigned bt = find_root(b);
        if (at != bt) {
            roots[at] = bt;
            --tree_cnt;
        }
    }

    bool is_DAG() { return tree_cnt == 1; }
};

int main() {
    unsigned n, m;
    scanf("%u%u", &n, &m);
    Union graph(n);
    for (unsigned i = 0; i < m; ++i) {
        unsigned a, b;
        scanf("%u%u", &a, &b);
        graph.connect(a, b);
    }
    printf("%s\n", graph.is_DAG() ? "yes" : "no");
}

我用bfs为什么通不过第二个测试点呃？难道是时间复杂度太高了？那应该用什么数据结构呢？

先排序,再遍历.可以不用BFS

include

using namespace std ;

struct pairs {
int a,b ;
};
bool comp (const pairs & c, const pairs & d);
pairs num [1000001] ;
bool ok [1000001] = {0} ;
int main (){
int n,m,i ;
cin >> n >> m;
int front,back ;
for (i =0;i > front >> back ;
num[i].a = (front > back) ? back : front;
num[i].b = (front > back) ? front :back ;
}
sort (num,num+m,comp) ;
if (num [0].a != 1){
cout << “no” << endl ;
return 0;
}
ok [num[0].a] = 1 ;
ok [num[0].b] = 1 ;
int cnt ;
if (num[0].a == num[0].b)
cnt = n -1 ;
else
cnt = n -2 ;
bool flag = 0;
for (i =1;i <n;i ++){
if (ok [num[i].a] == 1){
if (ok [num[i].b] == 0){
ok [num[i].b] = 1 ;
cnt – ;
}
}
else {
if (ok [num[i].b] == 1){
ok [num[i].a] = 1 ;
cnt – ;
}
else {
flag = 1;
break ;
}
}
}
if (flag || cnt )
cout << “no” << endl ;
else
cout << “yes” << endl ;

}

bool comp (const pairs & c, const pairs & d){
if (c.a == d.a)
return c.b < d.b ;
return c.a < d.a ;
}