Mai intai trebuie sa te autentifici.
Cod sursa(job #782683)
Utilizator | Data | 28 august 2012 18:39:54 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.87 kb |
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define nmax 100010
int ind[nmax], lowLink[nmax], number = 1, N, M, X, Y;
bool InStack[nmax];
stack<int> S;
vector<int> G[nmax];
vector<vector<int> > CTC;
void Tarjan (int node)
{
ind[node] = lowLink[node] = number ++;
S.push(node);
InStack[node] = true;
for(vector<int> :: iterator it = G[node].begin(); it != G[node].end(); ++it)
{
if(!ind[*it])
{
Tarjan(*it);
lowLink[node] = min(lowLink[node], lowLink[*it]);
}else
{
if(InStack[*it])
lowLink[node] = min(lowLink[node], ind[*it]);
}
}
if(ind[node] == lowLink[node])
{
vector<int> NewComp;
int crt = 0;
while(crt != node)
{
crt = S.top();
S.pop();
InStack[crt] = false;
NewComp.push_back(crt);
}
CTC.push_back(NewComp);
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int i, j;
scanf("%i %i", &N, &M);
for(i = 1; i <= M; i++)
{
scanf("%i %i", &X, &Y);
G[Y].push_back(X);
}
for(i = 1; i <= N; i++)
if(!ind[i])
Tarjan(i);
printf("%i\n", CTC.size());
for(i = 0; i < CTC.size(); i++)
{
for(j = 0; j < CTC[i].size(); j++) printf("%i ", CTC[i][j]);
printf("\n");
}
return 0;
}