Mai intai trebuie sa te autentifici.
Cod sursa(job #1521848)
Utilizator | Data | 10 noiembrie 2015 21:37:33 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.04 kb |
#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");
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(){
ios_base::sync_with_stdio(false);
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";
}
}