Pagini recente » Cod sursa (job #1739924) | Cod sursa (job #2041489) | Cod sursa (job #1566997) | Cod sursa (job #410514) | Cod sursa (job #2055554)
#include<fstream>
#include<list>
#include<stack>
#include<bitset>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX=100005;
list<int>g[NMAX],scc[NMAX];
stack<int>s;
int scctime[NMAX],low_time[NMAX],n,m,k,node_time;
bitset<NMAX>in_stack;
void read_data(){
int from,to;
fin>>n>>m;
while(m--){
fin>>from>>to;
g[from].push_back(to);
}
}
void tarjan(int node){
scctime[node]=low_time[node]=++node_time;
s.push(node);
in_stack[node]=true;
list<int>::iterator it;
for(it=g[node].begin();it!=g[node].end();++it)
if(!scctime[*it]){
tarjan(*it);
low_time[node]=min(low_time[node],low_time[*it]);
}
else if(in_stack[*it])
low_time[node]=min(low_time[node],low_time[*it]);
if(scctime[node]==low_time[node]){
++k;
int sccnode;
do{
sccnode=s.top();
s.pop();
scc[k].push_back(sccnode);
in_stack[sccnode]=false;
}while(node!=sccnode);
}
}
void go_through_vertices(){
int i;
for(i=1;i<=n;++i)
if(!scctime[i])
tarjan(i);
}
void print(){
fout<<k<<'\n';
int i;
list<int>::iterator it;
for(i=1;i<=k;++i){
for(it=scc[i].begin();it!=scc[i].end();++it)
fout<<*it<<' ';
fout<<'\n';
}
}
int main(){
read_data();
go_through_vertices();
print();
}