Pagini recente » Cod sursa (job #2213448) | Cod sursa (job #1745484) | Cod sursa (job #2674128) | Cod sursa (job #1512618) | Cod sursa (job #1521845)
#include <vector>
#include <fstream>
#include <algorithm>
#include <bitset>
using namespace std;
vector<int> No[100001];
vector<vector<int>> conc;
int index[100001], lowlink[100001], st[100001], len=0,ind=1,k;
bitset<100001> v;
ifstream f("ctc.in");
ofstream of("ctc.out");
ios_base::sync_with_stdio(false);
void dfs(const int& x){
index[x] = ind;
lowlink[x] = ind++;
st[len++] = x;
v[x] = 1;
for (const auto&j : No[x]){
if (!index[j]){
dfs(j);
lowlink[x] = min(lowlink[x], lowlink[j]);
}
else if (v[j]) lowlink[x] = min(lowlink[x], index[j]);
}
if (lowlink[x] == index[x]){
conc.push_back(vector<int>());
do{
k = st[--len];
v[k] = 0;
conc[conc.size() - 1].push_back(k);
} while (x != k);
}
}
int main(){
int N, M,a,b;
f >> N >> M;
for (int i = 0; i < M; ++i){
f>>a>>b;
No[a].push_back(b);
}
for (int i = 1; i <= N;++i)
if (!index[i])dfs(i);
of << conc.size()<<"\n";
for (const auto&j:conc){
for (const auto&d : j)
of << d << " ";
of << "\n";
}
}