Pagini recente » Cod sursa (job #351751) | Cod sursa (job #1940808) | Cod sursa (job #2386736) | Cod sursa (job #1896661) | Cod sursa (job #371772)
Cod sursa(job #371772)
//Kosaraju
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#define MAXN 100010
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
vector<int> G[2][MAXN];
stack<int> S;
int used[MAXN],WhatComp[MAXN],NComps;
vector< vector< int > > Comps;
int N,M;
void get_input(){
fi>>N>>M;
int x,y;
for (int i=1;i<=M;++i){
fi>>x>>y;
G[0][x].push_back(y);
G[1][y].push_back(x);
}
fi.close();
}
void DFPlus(int nod, vector<int>* G){
used[nod]=1;
for (vector<int>::iterator it=G[nod].begin();it!=G[nod].end();++it)
if (!used[*it])
DFPlus(*it,G);
S.push(nod);
}
void DFMinus(int nod,vector<int>* G,int comp){
WhatComp[nod]=comp;
for (vector<int>::iterator it=G[nod].begin();it!=G[nod].end();++it)
if (!WhatComp[*it])
DFMinus(*it,G,comp);
}
void get_output(){
fo<<NComps<<"\n";
for (int i=0;i<NComps;++i){
for (vector<int>::iterator it=Comps[i].begin();it!=Comps[i].end();++it)
fo<<*it<<" ";
fo<<"\n";
}
}
int main(){
get_input();
memset(used,0,sizeof(used));
memset(WhatComp,0,sizeof(WhatComp));
for (int i=1;i<=N;++i) if (!used[i]) DFPlus(i,G[0]);
NComps=0;
while (!S.empty()){
if (!WhatComp[S.top()]) { ++NComps; DFMinus(S.top(),G[1],NComps); }
S.pop();
}
Comps.resize(NComps);
for (int i=1;i<=N;++i) Comps[WhatComp[i]-1].push_back(i);
get_output();
return 0;
}