Pagini recente » Clasamentul arhivei de probleme | Cod sursa (job #1654478) | Cod sursa (job #2762910) | Cod sursa (job #2540609) | Cod sursa (job #1646958)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
void dfs(const int cur, const vector<vector<int> >& graf, vector<int>& st, vector<bool>& e_viz){
e_viz[cur] = true;
for(int i = 0; i < graf[cur].size(); ++i){
const int next = graf[cur][i];
if(!e_viz[next]){
dfs(next, graf, st, e_viz); } }
st.push_back(cur); }
void first_step(const int n, const vector<vector<int> >& graf, vector<int>& st){
vector<bool> e_viz(n, false);
for(int i = 0; i < n; ++i){
if(!e_viz[i]){
dfs(i, graf, st, e_viz); } } }
void second_step(const int n, const vector<vector<int> >& graf_t, vector<int>& st,
vector<vector<int> >& rez){
vector<bool> e_viz(n, false);
while(!st.empty()){
const int cur = st.back();
st.pop_back();
if(!e_viz[cur]){
rez.push_back(vector<int>(0, 0));
dfs(cur, graf_t, rez.back(), e_viz); } } }
int main(){
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
f >> n >> m;
vector<vector<int> > graf(n), graf_t(n);
for(int i = 0, a, b; i < m; ++i){
f >> a >> b;
--a, --b;
graf[a].push_back(b);
graf_t[b].push_back(a); }
vector<int> st;
first_step(n, graf, st);
vector<vector<int> > rez;
second_step(n, graf_t, st, rez);
g << rez.size() << endl;
for(int i = 0; i < rez.size(); ++i){
sort(rez[i].begin(), rez[i].end());
for(int j = 0; j < rez[i].size(); ++j){
g << rez[i][j]+1 << ' '; }
g << '\n'; }
return 0; }