Pagini recente » Cod sursa (job #1816092) | Cod sursa (job #1019759) | Cod sursa (job #2484460) | Cod sursa (job #2830060) | Cod sursa (job #946226)
Cod sursa(job #946226)
#include<vector>
#include<fstream>
#include<stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N, M;
vector<int> *G, *GT, aux;
vector<char> viz;
stack<int> st;
vector<vector<int>> comp_conexe;
void DF(int nod) {
viz[nod] = 1;
for(auto it = G[nod].begin(), it2 = G[nod].end(); it!=it2; ++it)
if(!viz[*it])
DF(*it);
st.push(nod);
}
void DF2(int nod) {
aux.push_back(nod);
viz[nod] = -1;
for(auto it = GT[nod].begin(), it2 = GT[nod].end(); it!=it2; ++it)
if(viz[*it] != -1)
DF2(*it);
}
int main() {
int i, x, y, nod;
f >> N >> M;
G = new vector<int>[N+1];
GT = new vector<int>[N+1];
viz.resize(N+1);
fill(viz.begin(), viz.end(), 0);
while(M--) {
f >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(i=1; i<=N; ++i)
if(!viz[i])
DF(i);
while(!st.empty()) {
nod = st.top();
st.pop();
if(viz[nod] != -1) {
DF2(nod);
comp_conexe.push_back(aux);
aux.clear();
}
}
g << comp_conexe.size() << "\n";
for(i=0; i<comp_conexe.size(); ++i) {
for(auto it = comp_conexe[i].begin(), it2 = comp_conexe[i].end(); it!=it2; ++it)
g << *it << " ";
g << "\n";
}
f.close();
g.close();
return 0;
}