Pagini recente » Cod sursa (job #1290828) | Cod sursa (job #2500321) | Cod sursa (job #3294721) | Cod sursa (job #243102) | Cod sursa (job #1427990)
#include <fstream>
#include <list>
using namespace std;
ifstream f1("ctc.in");
ofstream f2("ctc.out");
#define MX 100100
struct vertex
{
int index, lowlink;
bool onStack;
list<int> vecini;
};
vertex graf[MX];
int n,m, Index, S[MX], k, n_scc;
list<int> SCC[MX];
void strongconnect(int v)
{
graf[v].index= Index;
graf[v].lowlink= Index;
graf[v].onStack= true;
Index++;
S[++k]= v;
for (list<int>::iterator w= graf[v].vecini.begin(); w != graf[v].vecini.end(); ++w )
if ( graf[*w].index == 0 )
{
strongconnect(*w);
graf[v].lowlink= min( graf[v].lowlink, graf[*w].lowlink );
}
else
if ( graf[*w].onStack )
graf[v].lowlink= min(graf[v].lowlink, graf[*w].index);
if ( graf[v].lowlink == graf[v].index ) // i am in the root of the SCC, give 'em hell
{
n_scc++;
int w;
do
{
w= S[k--];
SCC[n_scc].push_back(w);
graf[w].onStack= false;
}
while ( w != v );
}
}
int main()
{
int i, x,y;
f1>>n>>m;
for (i=1; i<=m; i++)
{
f1>>x>>y;
graf[x].vecini.push_back(y);
}
Index= 1;
for (i=1; i<=n; i++)
if ( !graf[i].index )
strongconnect(i);
f2<<n_scc<<"\n";
for (i=1; i<= n_scc; i++)
{
for (list<int>::iterator it= SCC[i].begin(); it != SCC[i].end(); ++it )
f2<<*it<<" ";
f2<<"\n";
}
f2.close();
return 0;
}