Pagini recente » Cod sursa (job #1361467) | Cod sursa (job #2466653) | Cod sursa (job #1326149) | Cod sursa (job #2451183) | Cod sursa (job #940846)
Cod sursa(job #940846)
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<sstream>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<fstream>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
using namespace std;
#define pb push_back
#define mp make_pair
#define Y second
#define X first
#define fi freopen("input.txt","r",stdin)
#define fo freopen("output.txt","w",stdout)
const double pi = acos(-1.0);
const double eps = 1e-8;
/*Solution code starts here */
/*
ios_base::sync_with_stdio(false);
*/
#define MAX_V 100000
vector<int> L[MAX_V],C[MAX_V];
int V,dfsPos,dfsNum[MAX_V],lowlink[MAX_V],num_scc;
bool in_stack[MAX_V];
stack<int> S;
void tarjan(int v){
dfsNum[v] = lowlink[v] = dfsPos++;
S.push(v); in_stack[v] = true;
for(int i = L[v].size()-1;i>=0;--i){
int w = L[v][i];
if(dfsNum[w]==-1){
tarjan(w);
lowlink[v] = min(lowlink[v],lowlink[w]);
}else if(in_stack[w]) lowlink[v] = min(lowlink[v], lowlink[w]);
}
if(dfsNum[v]==lowlink[v]){
vector<int> com;
int aux;
do{
aux = S.top(); S.pop();
com.push_back(aux);
in_stack[aux] = false;
}while(aux!=v);
C[num_scc] = com;
++num_scc;
}
}
void build_scc(){
memset(dfsNum,-1,sizeof(dfsNum));
memset(in_stack,false,sizeof(in_stack));
dfsPos = num_scc = 0;
for(int i = 0;i<V;++i)
if(dfsNum[i]==-1)
tarjan(i);
}
int main()
{
int ed,a,b;
ios_base::sync_with_stdio(false);
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
cin>>V>>ed;
for(int i=1;i<=ed;i++)
{ cin>>a>>b;
a--;b--;
L[a].pb(b);
}
build_scc();
cout<<num_scc<<"\n";;
for(int i=0;i<num_scc;i++)
{
for(int j=0;j<C[i].size();j++)
cout<<C[i][j]+1<<" ";
cout<<endl;
}
return 0;
}