Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define L(i, m, n) for(int i(m);i < n;i++)
- #define pb push_back
- #define D(X) cout<<" "<<#X": "<<X<<endl;
- #define in(x) cin >> x
- #define SZ(X) int(X.size())
- #define clr(A, V) L(i, 0, SZ(A) A[i]=V
- #define ff first
- #define ss second
- #define RF(X) freopen(X, "r", stdin)
- #define WF(X) freopen(X, "w", stdout)
- using namespace std;
- typedef long long ll;
- typedef pair<ll,ll> pll;
- typedef vector<int> vi;
- typedef vector<vi> vii;
- typedef pair<int,int> pii;
- typedef vector<pii> vpii;
- typedef pair<int, string> pis;
- typedef vector<string> vs;
- typedef pair<pair<int, int>, pair<int, int > > piiii;
- const int MAXX=105;
- bool vis[MAXX],AP[MAXX];
- int parent[MAXX],low[MAXX],disc[MAXX];
- int tim=0;
- vii adj(MAXX,vi());
- void init(){
- L(i,0,MAXX){
- vis[i]=AP[i]=0;parent[i]=-1;
- adj[i].clear();
- low[i]=0;
- }
- tim=0;
- }
- void dfs(int u){
- vis[u]=1;
- low[u]=disc[u]=++tim;
- int child=0;
- L(i,0,SZ(adj[u])){
- int v=adj[u][i];
- if(!vis[v]){
- child++;
- parent[v]=u;
- dfs(v);
- low[u]=min(low[v],low[u]);
- if(parent[u]!=-1 && low[v]>=disc[v])
- AP[u]=1;
- if(parent[u]==-1 && child > 1)
- AP[u]=1;
- /** in case of bridges if(low[u] > disc[v]) add edge u,v**/
- }
- else if(v!=parent[u]){low[u]=min(low[u],disc[v]);}/****/
- }
- }
- int main(){
- // WF("out.txt");
- int n;
- while(in(n)){
- if(!n)return 0;init();
- string s;
- getline(cin, s);
- while(1){
- getline(cin, s);
- if(s=="0")break;
- string temp;vi a;
- L(i,0,SZ(s)){
- if(s[i]==' '){
- int x;
- stringstream ss; ss << temp; ss >> x; a.pb(x);
- temp.clear();
- }
- else{
- temp+=s[i];
- }
- }
- if(SZ(temp)){
- int x;
- stringstream ss; ss << temp; ss >> x; a.pb(x);
- }
- L(i, 1, SZ(a))
- adj[a[0]].pb(a[i]), adj[a[i]].pb(a[0]);
- }
- L(i,1,n+1){ if(!vis[i]) dfs(i);}
- int ans=0;
- L(i,1,n+1)if(AP[i])ans++;
- cout << ans <<endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment