Pagini recente » Cod sursa (job #2434977) | Cod sursa (job #2138337) | Cod sursa (job #632986) | Cod sursa (job #414867) | Cod sursa (job #2186767)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
vector<int> graph[100005];
stack<int> s;
bool in_stack[100005];
int low[100005];
int idx[100005];
int n,m,x,y,index,nr=0;
int min(int a,int b) {
return a<b?a:b;
}
void tarjan(int u) {
idx[u]=index;
low[u]=index;
index=index+1;
s.push(u);
in_stack[u]=true;
for (int v=0;v<graph[u].size();v++) {
if (idx[graph[u][v]]==-1) {
tarjan(graph[u][v]);
low[u]=min(low[u],low[graph[u][v]]);
}
else if (in_stack[graph[u][v]])
low[u]=min(low[u],idx[graph[u][v]]);
}
if (low[u]==idx[u])
nr++;
}
void ctc_tarjan() {
index=0;
for (int i=1;i<=n;i++) {
in_stack[i]=false;
low[i]=0;
idx[i]=-1;
}
for (int i=1;i<=n;i++) {
if (idx[i]==-1)
tarjan(i);
}
}
int main() {
in>>n>>m;
for (int i=0;i<m;i++) {
in>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
ctc_tarjan();
out<<nr<<endl;
in.close();
out.close();
return 0;
}