我一直以为dfs是O(n^2)的。
我是那么想的：\

//省略头文件
//省略定义变量
using namespace std;
void dfs(int x){
	vis[x]=1;
	for(int i=1;i<=n;i++)
     if(mp[x][i]&&!vis[i]){
          vis[i]=1;
          mp[x][i]=0;
          mp[i][x]=0;
          dfs(i);
	}
   return;
}
//省略主函数

每个dfs里都有一个for循环，所以dfs一次是O(n)的，每个点都要被dfs一次，所以乘起来是O(n^2)的。
但我在做P1434时，发现1<=n<10^6,于是我问了同班同学UnAccepting自动机，为什么深搜是O(n)的，于是他很耐心地给我讲，然后……他被我绕进去了。
所以哪位大佬能说明一下为什么dfs是O(n)的，解救一下我和那位努力把话题转移到并查集上的同班同学。
注：本人是五四学制初一，学信息学不到一年，不要讲一些太深奥的东西，谢谢。