Submission #8878035
Source Code Expand
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <numeric>
#include <random>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
void dfs(int now, int N, vector<bool> &seen, vector<vector<bool>> &graph){
seen[now]=true;
REP(i,N){
if(graph[now][i] && !seen[i]){
dfs(i, N, seen, graph);
};
}
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int N,M,ans=0;
cin>>N>>M;
vector<vector<bool>> graph(N,vector<bool>(N));
vector<int>a(M),b(M);
REP(i,M){
cin>>a[i]>>b[i];
a[i]--;b[i]--;
graph[a[i]][b[i]]=true;
graph[b[i]][a[i]]=true;
}
REP(i,M){
graph[a[i]][b[i]]=false;
graph[b[i]][a[i]]=false;
vector<bool>seen(N);
dfs(0,N,seen,graph);
bool flag=false;
REP(i,N){
if(seen[i]==false)flag=true;
}
ans+=flag;
graph[a[i]][b[i]]=true;
graph[b[i]][a[i]]=true;
}
cout<<ans<<endl;
}
Submission Info
Submission Time |
|
Task |
C - Bridge |
User |
betit0919 |
Language |
C++14 (GCC 5.4.1) |
Score |
300 |
Code Size |
1617 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
300 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_1.txt |
AC |
1 ms |
256 KB |
subtask_1_10.txt |
AC |
1 ms |
256 KB |
subtask_1_11.txt |
AC |
1 ms |
256 KB |
subtask_1_12.txt |
AC |
1 ms |
256 KB |
subtask_1_13.txt |
AC |
1 ms |
256 KB |
subtask_1_14.txt |
AC |
1 ms |
256 KB |
subtask_1_15.txt |
AC |
1 ms |
256 KB |
subtask_1_16.txt |
AC |
1 ms |
256 KB |
subtask_1_17.txt |
AC |
1 ms |
256 KB |
subtask_1_2.txt |
AC |
1 ms |
256 KB |
subtask_1_3.txt |
AC |
1 ms |
256 KB |
subtask_1_4.txt |
AC |
1 ms |
256 KB |
subtask_1_5.txt |
AC |
1 ms |
256 KB |
subtask_1_6.txt |
AC |
1 ms |
256 KB |
subtask_1_7.txt |
AC |
1 ms |
256 KB |
subtask_1_8.txt |
AC |
1 ms |
256 KB |
subtask_1_9.txt |
AC |
1 ms |
256 KB |