Pagini recente » Cod sursa (job #545719) | Cod sursa (job #2945420) | Cod sursa (job #1226646) | Cod sursa (job #85352) | Cod sursa (job #587214)
Cod sursa(job #587214)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define Nmax 100001
int N, M, viz[Nmax], st[Nmax], nrcomp, cnt;
vector<int> G[Nmax], Gt[Nmax], sol[Nmax];
stack<int> S;
void DF(int nod) {
if(viz[nod])
return;
viz[nod]=1;
for(vector<int>:: iterator it=G[nod].begin(); it!=G[nod].end(); ++it)
if(!viz[*it])
DF(*it);
S.push(nod);
}
void DF2(int nod) {
if(viz[nod]==-1)
return;
viz[nod]=-1;
st[++cnt]=nod;
for(vector<int>:: iterator it=Gt[nod].begin(); it!=Gt[nod].end(); ++it)
if(viz[*it]!=-1)
DF2(*it);
}
void add() {
int i;
nrcomp++;
for(i=1; i<=cnt; i++)
sol[nrcomp].push_back(st[i]);
}
int main() {
int i, j, nod;
f>>N>>M;
while(M--) {
f>>i>>j;
G[i].push_back(j);
Gt[j].push_back(i);
}
for(i=1; i<=N; i++)
if(!viz[i])
DF(i);
while(!S.empty()) {
nod=S.top();
cnt=0;
if(viz[nod]!=-1) {
DF2(nod);
add();
}
S.pop();
}
g<<nrcomp<<"\n";
for(i=1; i<=nrcomp; i++) {
for(vector<int>:: iterator it=sol[i].begin(); it!=sol[i].end(); ++it)
g<<*it<<" ";
g<<"\n";
}
f.close(); g.close();
return 0;
}