Pagini recente » Cod sursa (job #1418757) | Cod sursa (job #181593) | Cod sursa (job #1664748) | Cod sursa (job #1245720) | Cod sursa (job #1737772)
#include <fstream>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
unsigned int n,m,x,y,node,indx,nrComp=0;
int idx[100005];
int lowLink[100005];
int inStack[100005];
vector<int> graph[100005];
stack<int> st;
unsigned int min(unsigned int a,unsigned int b) {
if (a>=b)
return b;
return a;
}
void tarjan(unsigned int v) {
idx[v]=indx;
lowLink[v]=indx;
indx++;
st.push(v);
inStack[v]=1;
for (unsigned int u=0;u<graph[v].size();u++) {
if (idx[graph[v][u]]==-1) {
tarjan(graph[v][u]);
lowLink[v]=min(lowLink[v],lowLink[graph[v][u]]);
}
else if (inStack[graph[v][u]])
lowLink[v]=min(lowLink[v],idx[graph[v][u]]);
}
if (idx[v]==lowLink[v]) {
nrComp++;
}
}
void ctcTarjan() {
indx=0;
for (unsigned int i=1;i<=n;i++)
if (idx[i]==-1)
tarjan(i);
}
int main() {
memset(idx,-1,sizeof(idx));
memset(lowLink,0,sizeof(lowLink));
memset(inStack,0,sizeof(inStack));
in>>n>>m;
for (unsigned int i=0;i<m;i++) {
in>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
ctcTarjan();
out<<nrComp;
return 0;
}